Zmniejszenie P vs. NP do SAT

W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna.

Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów, prawdopodobnie jest to nieco niepoprawnie podane. Prosimy o wskazanie poprawek w swoich odpowiedziach.

W następującej pracy:
Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork i Moni Naor, SIAM Rev. 45, 727 (2003), DOI: 10.1137 / S0036144503429856 ,
autorzy piszą:

Załóżmy, że badacz A uzyskał dowód, że P ≠ NP i chce przekazać ten fakt profesorowi B. Załóżmy, że w celu ochrony siebie A potwierdza swoje roszczenie do B w sposób bez wiedzy ...

Istnieje kilka standardowych problemów związanych z NP-zupełnością, takich jak satysfakcja (SAT), Hamilton-Graph i Graph3-Colorability (G3C), dla których istnieją dowody braku wiedzy. Standardowym sposobem udowodnienia dowolnego twierdzenia NP jest najpierw sprowadzenie go do przykładu wyżej wymienionych problemów NP-zupełnych, a następnie przeprowadzenie dowodu braku wiedzy.

To pytanie dotyczy takiej redukcji. Załóżmy, że P vs. NP jest rozliczany na jeden z następujących sposobów:

P = NP
P ≠ NP
P vs. NP jest niezależny od standardowej teorii zbiorów aksomatycznych.

Niech σ oznacza dowód. Zatem P vs. NP jest w języku NP (ponieważ istnieje na to krótki dowód). Redukcja z twierdzenia (powiedzmy P ≠ NP) do problemu NP-zupełnego (powiedzmy SAT) jest niezależna od σ. To jest:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

To znacznie przekracza moją wyobraźnię! Wydaje się, że nawet jeśli otrzymamy dowód σ, jest mało prawdopodobne, abyśmy mogli zbudować taką formułę ϕ.

Czy ktoś mógłby rzucić na to trochę światła?

Ponadto niech L będzie językiem NP, w którym leży P vs. NP . Język składa się z nieskończenie wielu twierdzeń, takich jak P vs. NP , o dowolnych rozmiarach.

Co to jest kandydat na L?
Czy L może być NP-kompletny?

cc.complexity-theory complexity-classes np-hardness p-vs-np MS Dousti
źródło

Nie rozumiem tej części: „Niech σ oznacza dowód. Zatem P vs. NP jest w NP (ponieważ istnieje krótki dowód na to). Redukcja z twierdzenia (powiedzmy, P ≠ NP) do NP -kompletny problem (powiedzmy SAT) jest niezależny od σ. To znaczy: Istnieje wzór ϕ, który jest zadowalający wtedy i tylko wtedy, gdy P ≠ NP. ”. Czy mógłbyś wyjaśnić to trochę więcej? Nie ma dla mnie sensu, że „P vs NP jest w NP”, nawet jeśli zmienisz go na „czy istnieje dowód co najwyżej n w teorii T dla P \ neq NP”. Albo jest najmniejsza n taka, że na pytanie jest dowód takiej wielkości, albo nie ma takiego dowodu.

Kaveh

φ

$\varphi$

n

$n$

φ

$\varphi$

T

$T$

φ

$\varphi$

φ

$\varphi$

P \neq N P

$P \neq NP$

T

$T$

@Kaveh: Dodano wyjaśnienie.

MS Dousti

kilka interesujących pomysłów, ale nie ma sensu mówić, że „dowód jest w NP” lub że „istnieje krótki dowód”. tzn. mogłaby istnieć jakaś metoda tworzenia tych podobieństw, ale musiałaby być bardziej formalnie zdefiniowana. wydaje się, że najbliższe tym ideom byłyby ramy naturalnych dowodów razborov / rudich.

vzn

Odpowiedzi:

Sposób na sprawdzenie testowania wyrażeń matematycznych (np. Rozdzielczość P w porównaniu z NP) jako pytania o formę „jest formuła… zadowalająca” jest następujący:

Napraw jakiś system aksjomatów. Biorąc pod uwagę ciąg o długości n, czy ciąg jest dowodem wyrażenia matematycznego w systemie aksjomat, można coś zdefiniować w prosty sposób: ciąg powinien składać się z zdań. Każde zdanie powinno być albo aksjomatem, albo powinno wynikać z poprzednich zdań jedną z reguł wnioskowania.

Zdefiniowanie logicznej formuły, która to wszystko weryfikuje, nie stanowi problemu. Wszystko, co powinieneś wiedzieć, to długość n dowodu!

Dana Moshkovitz
źródło

P vs. NP jest w NP (ponieważ istnieje na to krótki dowód)

To nie ma dla mnie większego sensu. NP jest klasą złożoności problemów decyzyjnych, które mają dowolnie duże wystąpienia, a P vs. NP ich nie ma. Z tego, co powiesz później:

niech L będzie językiem NP, w którym leży P vs. NP.

możesz zamiast tego oznaczać, że P vs. NP jest wystąpieniem problemu NP; ale oczywiście tak jest! Jest to również przypadek nieskończonej liczby problemów P, DTIME (n) itp. W szczególności oto dwóch kandydatów DTIME (1) na L, dokładnie jeden z nich jest poprawny: zawsze wracaj true; lub zawsze wracaj false.

Aleksiej Romanow
źródło

Przeczytaj ponownie notatkę dodatkową na początku pytania. Mówiłem to nieformalnie, co prowadzi do waszego zamieszania. Aby sformalizować, należy rozważyć uogólnienie twierdzenia „P vs. NP”. Dla nieskończenie wielu n uogólnienie zakłada twierdzenie o długości n. Twierdzenia te powodują powstanie języka L, którego nie da się ustalić w DTIME (1).

MS Dousti

Zatem krótki dowód / odrzucenie „P vs. NP” to tylko jeden przypadek „uogólnionego P vs. NP” (być może łatwy?) I nie wynika z tego, że GPvNP jest w NP.

Aleksiej Romanow

Z góry: Rozumiem sprzeciw wobec sposobu, w jaki sformułowane jest pierwsze cytowane zdanie, ponieważ członkowie NP są zbiorami, a „P vs. NP” nie jest zbiorem. Jednak w przypadku drugiego zarzutu każdy „problem NP” jest problemem decyzyjnym, który zawsze może być zgodnie z prawem sformułowany jako decyzja, czy łańcuch znaków jest w języku; Nie widzę nic złego w jego definicji L. Ponadto, odwołanie się do trywialnych, zawsze prawdziwych lub zawsze fałszywych języków DTIME (1) ignoruje istotę: jeśli znamy WSZYSTKIE prawdziwe stwierdzenia, prawdopodobnie budujemy wygląd stół do maszyny Turinga, aby uzyskać dostęp do stałego czasu.

Daniel Apon

[Kontynuuj] Ale zakładając, że L jest właściwym językiem (tj. Zestawem nieskończonym), wtedy zakładasz nieskończenie dużą tabelę „prawdziwych instrukcji”, do której dostęp, który wydaje się łamać wszelkie reguły. Lub bardziej do rzeczy: dlaczego twój argument za DTIME (1) nie uogólnia na ŻADNY język, nie tylko ten dziwny, który rozważamy teraz?

Daniel Apon

L \in D T I M E (1)

$L \in DTIME(1)$