Konsekwencje UP są równe NP

EDYCJA na 2011/02/08: Po znalezieniu i przeczytaniu niektórych odniesień postanowiłem rozdzielić oryginalne pytanie na dwa osobne. Oto część dotycząca UP vs NP, w części dotyczącej klas syntaktycznych i semantycznych zobacz Korzyści dla klas syntaktycznych i semantycznych .

$\mathsf{UP}$ (jednoznaczny czas wielomianowy, patrzwikiizoodla odniesienia) jest zdefiniowany jako języki ustalone przez maszyny $\mathsf{NP}$ z dodatkowym ograniczeniem, które

Istnieje co najwyżej jedna akceptująca ścieżka obliczeniowa dla dowolnego wejścia.

Dokładne relacje między a i vs są nadal otwarte. Wiemy, że funkcje jednokierunkowe w najgorszym przypadku istnieją tylko wtedy, gdy , i istnieją wyrocznie dotyczące wszystkich możliwości inkluzji . $\mathsf{P}$ $\mathsf{UP}$ $\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{P} \neq \mathsf{UP}$ $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$

Interesuje mnie, dlaczego vs jest ważnym pytaniem. Ludzie mają skłonność wierzyć (przynajmniej w literaturze ), że te dwie klasy są różne, a moim problemem jest: $\mathsf{UP}$ $\mathsf{NP}$

Jeśli , czy zdarzyły się jakieś „złe” konsekwencje? $\mathsf{UP} = \mathsf{NP}$

Istnieje podobny post na blogu złożoności w 2003 roku. I jeśli moje rozumowanie jest prawidłowe, wynik Hemaspaandra, Naik, Ogiwara i Selman pokazuje, że jeśli

Istnieje język taki, że dla każdej zadowalającej formuły istnieje unikalne, satysfakcjonujące przypisanie z w , $\mathsf{NP}$ $L$ $\phi$ $x$ $(\phi,x)$ $L$

następnie hierarchia wielomianowa zapada się na drugi poziom. Żadna taka implikacja nie jest znana, jeśli utrzymuje. $\mathsf{UP} = \mathsf{NP}$

cc.complexity-theory complexity-classes conditional-results unique-solution Hsien-Chih Chang 張顯之
źródło

(1) Łatwo jest zauważyć (prawie z definicji), że UP i BPP mają pełne problemy, jeśli „problemy” mogą odnosić się do obiecanych problemów. Nie wiadomo, że mają pełne języki . (2) Nie znam dokładnej definicji klas składniowych. Czy PH jest składniowe? Nie ma pełnego problemu (nawet z obietnicą), chyba że załamie się hierarchia wielomianowa. (3) Nie znam twojego użycia zapisu „PromiseUP”. Jeśli NP oznacza klasę języków rozpoznawanych przez maszynę NP, a PromiseUP oznacza klasę problemów z obietnicą rozpoznawanych przez maszynę UP, to oczywiście nie mogą być one równe.

Tsuyoshi Ito,

@Tsuyoshi: Dziękuję za pytania. (1) Przez problemy rozumiem języki , to moja wina, że nie piszę tego wyraźnie. (2) Definiujemy klasy syntaktyczne jako charakteryzujące się językiem liścia na maszynach wielogodzinnych. PH jest szczególny, ponieważ nie jest znana żadna charakterystyka wieloetapowego języka liścia, w którym gwarantowane są naturalne pełne języki; ale PH mają charakterystykę języka liścia w przestrzeni logów . (więcej)

Hsien-Chih Chang 之之

(cd.) (3) Może użycie PromiseUP jest nieprawidłowe. Tutaj przez PromiseUP mam na myśli klasę języków , taką, że w przypadku wystąpienia tak maszyna ma unikalną ścieżkę akceptacji, aw żadnym przypadku maszyna nie ma zerowej lub co najmniej dwóch ścieżek akceptacji.

Hsien-Chih Chang 之之

Dziękuję za odpowiedź. Co do (3), pobieżnego spojrzenia na pracę Hemaspaandry, Naika, Ogihary i Selmana nie mogę znaleźć sposobu na określenie wyniku w kategoriach problemów decyzyjnych. BTW, link do papieru jest zepsuty. Oto link do wersji czasopisma .

Tsuyoshi Ito,

Aby się upewnić, PromiseUP różni się całkowicie od tego, co opisałeś. Jak napisałem, PromiseUP jest wersją UP związaną z obietnicą; oznacza to, że jest to klasa problemów z obietnicą, które mają niedeterministyczną maszynę Turinga w czasie wielomianowym M taką, że dla tak-instancji M ma dokładnie jedną ścieżkę akceptacji, a dla nie instancji M nie ma ścieżek akceptacji. Chociaż uważam, że PromiseUP to tradycyjna nazwa tej klasy, niektórzy ludzie (w tym ja) piszą tę klasę po prostu jako UP.

Tsuyoshi Ito,

Konsekwencje UP są równe NP

Odpowiedzi: