Nadzbiór wieloczęściowy NP kompletnego języka z nieskończenie wieloma ciągami wyłączonymi z niego

Czy dla dowolnego arbitralnego NP pełnego języka zawsze istnieje nadzbiór czasu policyjnego, którego dopełnienie jest również nieskończone?

Na stronie /cs//q/50123/42961 poproszono o trywialną wersję, która nie przewiduje, że nadzbiór ma nieskończone uzupełnienie.

Dla celów tej kwestii, można przyjąć, że . Jak wyjaśnił Vor, jeśli wówczas odpowiedź brzmi „Nie”. (Jeśli , to jest NP-zupełny. Oczywiste jest, że nie istnieje nadzbiór który jest nieskończony i ma nieskończony dopełnienie, ponieważ dopełnienie ma tylko jeden element.) W ten sposób możemy skupić się na przypadku .$P \ne NP$P = N P X = { x ∣ x ∈ N + ∧ x > 1 } X X P ≠ N $P = NP$$P = NP$$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$$X$$X$$P \ne NP$

Każdy -Complete zestaw zawiera nieskończoną podzbiór w P , przy założeniu, że$\mathsf{coNP}$$\mathsf{P}$

• istnieją pseudolosowe generatory i
• istnieją bezpieczne permutacje jednokierunkowe.

Innymi słowy, przy założeniu, że te dwa przypuszczenia są spełnione, nie -Complete zestawu jest P odpornościowego . Jak wskazano w komentarzach Lance'a, sugeruje to Twierdzenie 4.4 z$\mathsf{coNP}$

• Glasser, Pavan, Selman i Sengupta, „ Właściwości zestawów NP-zupełnych ”, SIAM J. Comput. 36 (2), 516–542.

(Kaveh już pokazał, że pytanie jest równoważna czy każdy -Complete zestawów zawiera nieskończoną P podzbiór. W innym języku, to mówi, że nie c O N P -Complete zestawu jest „ P -immune”. To jest językiem stosowanym w powyższym twierdzeniu).$\mathsf{coNP}$$\mathsf{P}$$\mathsf{coNP}$$\mathsf{P}$

Interesujące pytanie. Wyrok

dla każdego NP-kompletnego istnieje U w P, tak że L ⊆ U i U c są nieskończone.$L$$U$$L \subseteq U$$U^c$

jest równa:

dla każdego NP-kompletnego , uzupełnienie L zawiera nieskończony zbiór P.$L$$L$

co z kolei jest równoważne z

każdy kompletny zestaw coNP zawiera nieskończony zestaw P.

który jest symetrycznie taki sam jak

Nie sądzę, żeby odpowiedź była znana. Myślę, że naturalne kompletne zestawy NP spełniają ten warunek z łatwością. Nie sądzę, abyśmy mieli narzędzia do zbudowania sztucznego zestawu, który zawodzi stwierdzenie. (patrz komentarz Lance'a poniżej)