Poly tiempo superconjunto de lenguaje completo NP con infinitas cadenas excluidas de él

Para cualquier lenguaje NP arbitrario completo, ¿hay siempre un superconjunto polytime cuyo complemento también es infinito?

Se ha pedido una versión trivial que no estipula que el superconjunto tenga un complemento infinito en /cs//q/50123/42961

A los fines de esta pregunta, puede suponer que . Como explicó Vor, si entonces la respuesta es "No". (Si , entonces es NP-complete. Claramente no hay un superconjunto de que sea infinito y tenga un infinito complemento, ya que el complemento de tiene un solo elemento.) Por lo tanto, podemos centrarnos en el caso .P = N P P = N P X = { x ∣ x ∈ N + ∧ x > 1 } X X P ≠ N $P \ne NP$$P = NP$$P = NP$$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$$X$$X$$P \ne NP$

Cada conjunto completo de contiene un subconjunto infinito en P suponiendo$\mathsf{coNP}$$\mathsf{P}$

• existen generadores pseudoaleatorios, y
• existen permutaciones unidireccionales seguras.

En otras palabras, suponiendo que estos dos conjeturas son verdaderas, no conjunto -Complete es P- inmune . Como se señaló en los comentarios de Lance, esto está implícito en el Teorema 4.4 de$\mathsf{coNP}$

• Glasser, Pavan, Selman y Sengupta, " Propiedades de conjuntos completos de NP ", SIAM J. Comput. 36 (2), 516–542.

(Kaveh ya ha demostrado que su pregunta es equivalente a si cada conjunto completo de contiene un subconjunto P infinito . En otro lenguaje, esto significa que ningún conjunto completo de c o N P es " P- inmune". es el lenguaje utilizado en el teorema mencionado anteriormente).$\mathsf{coNP}$$\mathsf{P}$$\mathsf{coNP}$$\mathsf{P}$

Interesante pregunta. La declaración

por cada NP- completo , hay U en P de modo que L ⊆ U y U c son infinitos.$L$$U$$L \subseteq U$$U^c$

es equivalente a:

por cada NP- completa , el complemento de L contiene un conjunto P infinito.$L$$L$

que a su vez es equivalente a

cada conjunto completo de coNP contiene un conjunto P infinito.

que es por simetría lo mismo que

No creo que se sepa la respuesta. Creo que los juegos completos naturales NP satisfacen esta condición fácilmente. No creo que tengamos herramientas para construir un conjunto artificial que falle la declaración. (ver el comentario de Lance a continuación)