Czy kompletność / twardość NP musi być konstruktywna?

Czy istnieje o następujących właściwościach:$L\in {\bf NP}$

1. Wiadomo, że oznacza P = N P .$L\in {\bf P}$${\bf P}={\bf NP}$

2. Nie (znany) wielomian czas redukcji Turinga z (lub inne N P -Complete problemu) do l .$SAT$${\bf NP}$$L$

Innymi słowy, jeśli wielomianem algorytm czas oznacza załamanie N P do P , wtedy konieczne jest, że to „ogólnie twardość” od L do N P musi być jakoś c o w a n s t r u c t ı v e , w tym sensie, że powiedzmy, że S A T musi być redukowalne do L poprzez pewne określone zmniejszenie?$L$${\bf NP}$${\bf P}$$L$${\bf NP}$$constructive$$SAT$$L$

Tak, są takie zestawy, każdą -intermediate zestaw (każdy zespół, który jest w udokumentowany N P -intermediate zakładając P ≠ N P ), na przykład jeden konstrukt z SAT zastosowaniu twierdzenia Ladner.$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$

Należy pamiętać, że musi uważany za N P -intermediate problemu, ponieważ jest w N P ale nie jest kompletna dla niego. Należy również zauważyć, że są przy założeniu, że P ≠ N P inaczej nie ma takiego L jak każdy nietrywialne problemem byłaby kompletna dla N P czy N P = P . Ponadto podane przez ciebie warunki nie oznaczają kompletności, więc pytanie w pierwszej części nie jest tożsame z pytaniem o konstruktywność kompletności.$L$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$L$$\mathsf{NP}$$\mathsf{NP}=\mathsf{P}$

---

Jeśli chodzi o pytanie w tytule, czyli „robi -hardness być konstruktywna?”.$\mathsf{NP}$

Odpowiedź zależy od tego, co rozumiemy przez „konstruktywne”. Klasycznie problem decyzyjny definiuje się jako N P- twardy iff$A$$\mathsf{NP}$

$$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$$

co znaczy

$$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$$

I według twierdzenia Cooka jest to równoważne z

$$SAT \leq^\mathsf{P}_m A$$

co znaczy

$$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in A)$$

$A$$f$

Klasycznie, nawet gdy nie mamy konkretnej funkcji, istnieje funkcja mówiąca, że ​​niemożliwe jest, aby żadna funkcja nie była redukcją, jest równoważna z twierdzeniem, że jakaś funkcja jest redukcją. Aby mówić o konstruktywności, musimy być bardziej rozważni. Możemy na przykład mówić o stwierdzeniach, które można udowodnić klasycznie, ale nie konstruktywnie (np. Intuicjonizm, w którym sens ma inny stan wiedzy matematycznej, Google dla „idealnego matematyka” lub sprawdź to ).

Intuicyjnie wydaje mi się prawdopodobne, że możemy udowodnić takie stwierdzenie, używając dowodu sprzeczności i bez wyraźnej funkcji redukcji. Ale to nie znaczy, że nie ma konstruktywnego dowodu tego oświadczenia. Aby powiedzieć więcej, że nie istnieje żaden konstruktywny dowód, musimy być bardziej konkretni: dowody, w której teorii / systemie? co rozumiemy przez konstruktywny dowód?

$k$

„Izomorficzny” różni się od redukcji Turinga (w rzeczywistości jest znacznie słabszy), ale te zestawy okazały się bezpośrednio trudne do NP i o ile wiem, nie ma znanej redukcji do SAT. To powiedziawszy, zgodnie z definicją kompletności NP musi istnieć pewna redukcja między tymi dwoma, więc chociaż spełnia to kryterium „nieznanej” redukcji, może nie być dokładnie tym, czego szukasz.

[1] Joseph, D. i Young, P. Kilka uwag na temat funkcji świadka dla zbiorów niepolominalnych i niekompletnych w NP. Informatyka teoretyczna. tom 39, str. 225--237. 1985. Elsevier.

Poniżej znajduje się przykład pytania w tytule. Został zaczerpnięty z następującego artykułu: Jan Kratochvil, Petr Savicky i Zsolt Tuza. Jeszcze jedno wystąpienie zmiennych powoduje, że satysfakcjonujący skok z trywialnego do np. Kompletnego. SIAM Journal on Computing, 22 (1): 203–210, 1993.

Niech f (k) będzie maksymalną liczbą całkowitą r tak, że każda forum k-SAT, w którym każda zmienna występuje co najwyżej r razy, jest zadowalająca. Nie wiadomo, czy f (k) jest obliczalne, chociaż znane są z tego stosunkowo wąskie granice (patrz H. Gebauer, R. Moser, D. Scheder i E. Welzl. Lokalna lemat i satysfakcja Lovasza. Efektywne algorytmy, strony 30–54, 2009.).

(k, s) -SAT jest problemem k-SAT ograniczonym do forumla, w którym każda zmienna występuje najczęściej.

Kratochvil i in. udowodniono, że (k, f (k) +1) -SAT jest NP-kompletny. Zauważ, że (k, f (k)) - problemy SAT są zawsze zadowalające (z definicji). Sama redukcja nie jest konstruktywna: zauważ, że redukcja generuje wzór, w którym każda zmienna występuje co najwyżej f (k) +1 razy, nawet jeśli nie wiadomo, że f (k) jest obliczalna. Główną niekonstruktywną ideą jest to, że chociaż wartość f (k) jest nieznana, istnieje formuła (k, f (k) +1) -SAT, która jest niezadowalająca i manipulują tą formułą zgodnie ze swoimi potrzebami .

Agrawal i Biswas przedstawili język NP-zupełny, dla którego nie jest znana redukcja Karp lub Cook. Dowód kompletności następuje, ponieważ jego relacja świadka jest uniwersalna (relacja świadka ma wymagane operatory łączenia i równoważności, które muszą być uniwersalne). Język podano w części 6.3 w piśmiennictwie.

M. Agrawal, S. Biswas, Universal relations in Proceedings IEEE Conferenceon Structure in Complexity Theory (1992), s. 207–220.