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 = NP$ $P = NP$ $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ $X$ $X$ $P \ne NP$

cc.complexity-theory np-complete structural-complexity

— ARi
źródło

Jeśli

jest NP-zupełny. Najwyraźniej nie ma nadzbioru

który jest nieskończony i ma nieskończone dopełnienie (zauważ, że

). Więc można „skupić się” na to, co się dzieje, jeśli

P = N P

$P = NP$

X = {x ∣ x \in N^{+} \land x > 1}

$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$

X

$X$

\bar{X} = {1}

$\bar{X} = \{1\}$

P \neq N P

$P \neq NP$

— Marzio De Biasi,

Jak o wersji zrelatywizowane: Czy jest wyrocznią st wszystkie ko-NP

zestawy są P -immune.

A

$A$

^{A}

$^A$

^{A}

$^A$

— Lance Fortnow,

@LanceFortnow ... lub dla dowolnego kompletnego języka w danym języku. Klasa złożoności, czy zawsze istnieje nietrywialny nadzbiór o mniejszej złożoności.

— ARi

Odpowiedzi:

Każdy -Complete zestaw zawiera nieskończoną podzbiór w , 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ą podzbiór. W innym języku, to mówi, że nie -Complete zestawu jest „ -immune”. To jest językiem stosowanym w powyższym twierdzeniu). $\mathsf{coNP}$ $\mathsf{P}$ $\mathsf{coNP}$ $\mathsf{P}$

— Joshua Grochow
źródło

Projekt ECCC

— Kaveh

Dzięki silnym funkcjom hard-core (i iteracji ) permutacje jednokierunkowe oznaczają generatory pseudolosowe.

@RickyDemer: patrz definicje 4.1-4.3 w cytowanym artykule. Jeśli dobrze rozumiem, OWP implikują to, co nazywają „krypto-PRG”, ale niekoniecznie to, co nazywają „PRG” w pracy Glasser-Pavan-Selman-Sengupta. Do swojego wyniku (wydają się) potrzebują zarówno OWP, jak i tego, co nazywają PRG.

— Joshua Grochow,

Kaveh wykazał jedynie równoważność z kompletami ko-NP-kompletnymi odpornymi na P, ale wniosek twierdzenia 4.4 w Glasser i in., Że wszystkie zestawy NP-kompletne muszą mieć redukcję długości, oznacza również, że nie ma ko-NP- kompletne zestawy odporne na P.

— Lance Fortnow,

@JoshuaGrochow Dzięki ... ale czy możemy przyjąć pewne założenia, które z kolei sugerują brak takiego języka. Bardziej interesowały mnie scenariusze, w których nie istnieje

— nadzbiór

Interesujące pytanie. Wyrok

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

jest równa:

dla każdego NP-kompletnego , uzupełnienie 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~~

~~każdy komplet NP zawiera nieskończony zestaw P.~~

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)

— Kaveh
źródło

Twoje wstępne stwierdzenie jest trywialnie prawdziwe. (Niech U będzie pełna języka.)

To interesujący ciąg dedukcji ... Czy możesz podać przykład naturalnego języka NP w tym zakresie

— ARi

Symetria nie ma sensu. Na przykład, każdy zestaw ce ma nieskończony, obliczalny podzbiór, ale istnieją zestawy, które tego nie mają.

— Lance Fortnow,