Jakie mamy dowody na ?

Zgodnie z sugestią Josha Grochowa przekształcam swój komentarz z poprzedniego pytania w nowe pytanie.

Jakie mamy dowody na ? $\mathsf{UP} \neq \mathsf{NP}$

Tutaj to klasa języków rozpoznawalnych przez niedeterministyczne maszyny Turinga o wielomianowym czasie, które mają unikalną ścieżkę akceptacji w instancjach „tak” i brak ścieżki akceptacji w instancjach „nie”. $\mathsf{UP}$

Oczywiście , ale dlaczego mielibyśmy sądzić, że przechowywanie jest surowe? Dowodem, który mogę znaleźć, jest separacja wyroczni : podlega losowej wyroczni, . Zoo złożoności sugeruje również, że nie uważa się , że ma pełne problemy. $\mathsf{UP} \subseteq \mathsf{NP}$ $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$ $\mathsf{UP}$

— Sasho Nikolov
źródło

Powiązana dyskusja tutaj: cstheory.stackexchange.com/q/3887/1800

— Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之 hm, może moje pytanie jest zduplikowane. Jeśli tak uważasz, mogę zgłosić to do usunięcia.

— Sasho Nikolov

Nie sądzę, że to duplikat. Sądzę, że odpowiedzi na drugie pytanie będą się liczyły jako odpowiedzi na to pytanie, ale niekoniecznie na odwrót - mogą istnieć powody, by sądzić, że nie mają formy „ Jeśli , to nastąpi jakaś (inna) konsekwencja złej złożoności. "

N P \neq U P

$\mathsf{NP} \neq \mathsf{UP}$

N P = U P

$\mathsf{NP}=\mathsf{UP}$

— Joshua Grochow

Najlepszym dowodem jest to, że mamy sub wykładnicze górne granice niektórych naturalnych nierozwiązywalnych problemów w UP (takich jak wersje decyzyjne dyskretnego logarytmu i faktoryzacji liczb całkowitych), podczas gdy nie jesteśmy w stanie znaleźć takiej górnej granicy dla niektórych problemów z NP-zupełnością, takich jak 3SAT. Taka górna granica dla 3SAT jest niemożliwa przy założeniu wykładniczej hipotezy czasowej.

— Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Ale te problemy są w , więc jeśli , to nadal będą tylko w , więc nie byłoby -kompletny, chyba że ...

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

N P = U P

$\mathsf{NP} = \mathsf{UP}$

N P \cap c o N P

$\mathsf{NP} \cap \mathsf{coNP}$

N P

$\mathsf{NP}$

N P = c o N P

$\mathsf{NP} = \mathsf{coNP}$

— Joshua Grochow

Nawet Selman i Yacobi Przypuszcza się, że nie istnieje odłączony -pair tak, że wszystkie separatory są -hard o . Hipoteza ta sugeruje, że . $NP$ $(A, B)$ $(A, B)$ $\le_T^p$ $NP$ $UP \ne NP$

S. Even, A. Selman i J. Yacobi. Złożoność obiecujących problemów z aplikacjami do kryptografii z kluczem publicznym. Information and Control, 61: 159–173, 1984.

— Mohammad Al-Turkistany
źródło

Działa to również jako dobra odpowiedź na powiązany post cstheory.stackexchange.com/questions/3887/…

— Mohammad Al-Turkistany

Ta silna hipoteza sugeruje, że

N P \neq c o N P

$NP \ne coNP$

— Mohammad Al-Turkistany