Czy istnienie całkowitego problemu wyszukiwania

Łatwo zauważyć, że jeśli to istnieją całkowite problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa). $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ $\mathsf{NP}$

Czy odwrotna jest również prawda, tj

Czy istnienie całkowitego problemu wyszukiwania nierozwiązywalnego w czasie wielomianowym oznacza ? $\mathsf{NP}$ $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$

cc.complexity-theory reference-request search-problem

— Kaveh
źródło

Czy masz na myśli całkowity problem wyszukiwania z problemem decyzyjnym NP? Czy faktoryzacja liczb całkowitych jest takim problemem?

— Mohammad Al-Turkistany

Myślę, że ma na myśli TFNP.

— domotorp

Odpowiedzi:

Zakładam, że P, NP i coNP w pytaniu są klasami języków, a nie klasami problemów z obietnicą. W tej odpowiedzi używam tej samej konwencji. (Na wszelki wypadek, jeśli mówimy o klasach problemów z obietnicą, odpowiedź jest twierdząca, ponieważ P = NP∩coNP jako klasy problemów z obietnicą jest równoważne P = NP.)

Wtedy odpowiedź jest negatywna w relatywizowanym świecie.

Stwierdzenie TFNP ⊆ FP jest znane w literaturze jako Twierdzenie Q [FFNR03]. Istnieje słabsze stwierdzenie o nazwie Propozycja Q ' [FFNR03], że każda całkowita relacja NPMV z odpowiedziami jednobitowymi jest w FP. (Tutaj relacja z odpowiedziami jednobitowymi oznacza podzbiór {0,1} ^* × {0,1}). Łatwo zauważyć, że Twierdzenie Q w stosunku do niektórych wyroczni implikuje Twierdzenie Q 'w odniesieniu do tej samej wyroczni.

Fortnow i Rogers [FR02] rozważyli związki między stwierdzeniem P = NP∩coNP, Twierdzeniem Q ', a kilkoma innymi powiązanymi stwierdzeniami w relatywizowanych światach. W szczególności Twierdzenie 3.2 (lub Twierdzenie 3.3) w [FR02] implikuje, że istnieje wyrocznia, w stosunku do której P = NP∩coNP, ale Twierdzenie Q 'nie ma (a zatem Twierdzenie Q też nie ma). Dlatego w relatywizowanym świecie P = NP∩coNP nie implikuje Twierdzenia Q; lub przyjmując przeciwnie, istnienie relacji TFNP, której nie można obliczyć w czasie wielomianowym, nie implikuje P ≠ NP∩coNP.

Bibliografia

[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik i John D. Rogers. Odwracanie na funkcje. Informacje i obliczenia , 186 (1): 90–103, październik 2003 r. DOI: 10.1016 / S0890-5401 (03) 00119-6 .

[FR02] Lance Fortnow i John D. Rogers. Rozdzielność i funkcje jednokierunkowe. Złożoność obliczeniowa , 11 (3–4): 137–157, czerwiec 2002 r. DOI: 10.1007 / s00037-002-0173-4 .

— Tsuyoshi Ito
źródło

Dzięki Tsuyoshi. Istnieje również wynik w drugiej wersji problemu, który pokazuje, że odpowiedź jest tam zdecydowanie negatywna: Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo i Toniann Pitassi, „ The Relative Complexity of NP Search Problems ”, 1998

— Kaveh

C : 2^{n + 1} \to 2^{n}

$C:2^{n+1}\to2^n$

C

$C$

@Kaveh: Nie jestem pewien, czy rozumiem twoje pytanie w komentarzu. W świecie nierelatywizowanym jedynym sposobem na stwierdzenie, że „P = NP∩coNP” i „TFNP⊆FP” nie są równoważne, jest wykazanie, że to pierwsze utrzymuje i że drugie nie, chyba że udowodnimy logiczną niezależność wynik. Ale popularne jest przekonanie, że P ≠ NP∩coNP, co oznacza, że „P = NP∩coNP” i „TFNP⊆FP” są równoważne (ponieważ oba są fałszywe). Dlatego nie wiem, jakiego rodzaju przypuszczenia szukasz.

— Tsuyoshi Ito

T F N P

$\mathsf{TFNP}$

P^{N P \cap c o N P}

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

@Kaveh: Czy mówisz o nierówności między dwoma twierdzeniami „P = NP∩coNP” i „TFNP⊆FP”, czy też o nierówności między czymś innym?

— Tsuyoshi Ito

$NP \cap co-NP$

— domotorp
źródło

T F U P \neq F P ⟹ N P \cap c o N P \neq P ⟹ T F N P \neq F P

$\mathsf{TFUP} \neq \mathsf{FP}\implies \mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P} \implies \mathsf{TFNP} \neq \mathsf{FP}$

T F N P \neq F P ⟹ T F U P \neq F P

$\mathsf{TFNP} \neq \mathsf{FP} \implies \mathsf{TFUP} \neq \mathsf{FP}$

Nie mogę powiedzieć, że MY nie wiemy, ale na pewno nie wiem. Oczywiście, jeśli pozwolimy na losowe redukcje, możesz wykonać sztuczkę Valiant-Vazirani, a ostatnia implikacja również stanie się prawdą. (O ile się nie mylę ...)

— domotorp

F P

$\mathsf{FP}$

T F U P

$\mathsf{TFUP}$

T F N P

$\mathsf{TFNP}$

F P

$\mathsf{FP}$

Tak, doskonale.

— domotorp

Wygląda na to, że Valiant-Vazirani tutaj nie działa (a przynajmniej nie rozumiem, jak to działa). Problem polega na tym, że wynikiem jest obiecujący problem, np. SAT dla USAT. Potrzebujemy problemu niezwiązanego z obietnicą. I wydaje się, że istnieją powody, by sądzić, że te dwa nie powinny być równe. Zamieszczę nowe pytanie dotyczące TFNP i TFUP.

— Kaveh