Surensemble de temps poly du langage NP complet avec une infinité de chaînes exclues

Pour tout langage arbitraire NP complet, existe-t-il toujours un surensemble de polytimes dont le complément est également infini?

Une version triviale qui ne stipule pas que le sur-ensemble a un complément infini a été demandée à /cs//q/50123/42961

Aux fins de cette question, vous pouvez supposer que . Comme Vor l'a expliqué, si la réponse est "Non". (Si , alors est NP-complet. De toute évidence, il n'y a pas de sur-ensemble de qui est infini et a un complément infini, car le complément de n'a que un seul élément.) nous pouvons nous concentrer ainsi sur l'affaire . $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
la source

alors

est NP-complet. De toute évidence, il n'y a pas de surensemble de

qui est infini et a un complément infini (notez que

). Ainsi , vous pouvez « se concentrer » sur ce qui se passe si

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

Que diriez-vous de la version relativisée: y a-t-il un oracle

st tous les ensembles co-NP

sont P

immun.

A

$A$

^{A}

$^A$

^{A}

$^A$

Lance Fortnow

@LanceFortnow ... ou pour toute langue complète dans un particulier. Classe de complexité, y a-t-il toujours un surensemble non trivial de moindre complexité.

ARi

Réponses:

Chaque ensemble complet contient un sous-ensemble infini dans supposant que $\mathsf{coNP}$ $\mathsf{P}$

des générateurs pseudo-aléatoires existent, et
des permutations unidirectionnelles sûres existent.

En d' autres termes, en supposant que ces deux sont vraies conjectures, non ensemble -complete est P- immunitaire . Comme le soulignent les commentaires de Lance, cela est sous-entendu par le théorème 4.4 de $\mathsf{coNP}$

Glasser, Pavan, Selman et Sengupta, « Properties of NP-complete sets », SIAM J. Comput. 36 (2), 516-542.

(Kaveh a déjà montré que votre question équivaut à savoir si chaque ensemble complet contient un sous-ensemble infini . Dans une autre langue, cela signifie qu'aucun ensemble complet n'est " immun". est le langage utilisé dans le théorème référencé ci-dessus.) $\mathsf{coNP}$ $\mathsf{P}$ $\mathsf{coNP}$ $\mathsf{P}$

Joshua Grochow
la source

ECCC draft

Kaveh

Par de fortes fonctions de noyau dur (et itération ), les permutations unidirectionnelles impliquent des générateurs pseudo-aléatoires.

@RickyDemer: Voir les définitions 4.1-4.3 dans l'article cité. Si je comprends bien, les PRO supposent ce qu'ils appellent des «crypto-PRG», mais pas nécessairement ce qu'ils appellent des «PRG» dans le papier Glasser-Pavan-Selman-Sengupta. Pour leur résultat, ils ont (semble-t-il) besoin à la fois de PRO et de ce qu'ils appellent des PRG.

Joshua Grochow

Kaveh a seulement montré que l'équivalence avec les ensembles co-NP-complets est immunisée contre le P, mais la conclusion du théorème 4.4 dans Glasser et al. Que tous les ensembles NP-complets doivent avoir une réduction augmentant la longueur, implique également qu'il n'y a pas de co-NP- ensembles complets P-immun.

Lance Fortnow

@JoshuaGrochow Merci ... mais y a-t-il des hypothèses que nous pouvons faire qui impliquent à leur tour la non-existence d'un tel langage. J'étais plus intéressé par les scénarios où il n'y a pas de surensemble de temps poly

ARi

Question interessante. La déclaration

pour chaque NP-complet , il n'y a en P de telle sorte que et est infinie. $L$ $U$ $L \subseteq U$ $U^c$

est équivalent à:

pour chaque NP-complet , le complément de contient un ensemble P infini. $L$ $L$

qui est à son tour équivalent à

chaque ensemble complet coNP contient un ensemble P infini.

~~qui est par symétrie le même que~~

~~chaque ensemble NP-complet contient un ensemble P infini.~~

Je ne pense pas que la réponse soit connue. Je pense que les ensembles naturels NP-complets satisfont facilement à cette condition. Je ne pense pas que nous ayons des outils pour construire un ensemble artificiel qui échoue à la déclaration. (voir le commentaire de Lance ci-dessous)

Kaveh
la source

Votre déclaration initiale est trivialement vraie. (Soit U la langue complète.)

C'est une chaîne intéressante de déductions ... Pourriez-vous donner un exemple d'un langage complet NP naturel à cet égard

ARi

La symétrie n'a pas de sens. Par exemple, chaque ensemble de ce a un sous-ensemble calculable infini, mais il existe des co-ensembles qui n'en ont pas.

Lance Fortnow