15
$\begingroup$

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?

A trivial version which does not stipulate the superset to have infinite complement has been asked at https://cs.stackexchange.com/q/50123/42961

For purposes of this question, you can assume that $P \ne NP$. As Vor explained, if $P = NP$ then the answer is "No". (If $P = NP$, then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement, as the complement of $X$ has only a single element.) Thus we can focus on the case $P \ne NP$.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ If $P = NP$ then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement (note that $\bar{X} = \{1\}$). So you can "focus" on what happens if $P \neq NP$. $\endgroup$
    – Marzio De Biasi
    Dec 5, 2015 at 20:32
  • 3
    $\begingroup$ How about the relativized version: Is there an oracle $A$ s.t. all co-NP$^A$ sets are P$^A$-immune. $\endgroup$
    – Lance Fortnow
    Dec 10, 2015 at 13:41
  • $\begingroup$ @LanceFortnow ...or for any complete language in a particular. Complexity class, is there always a non trivial superset of a lesser complexity. $\endgroup$
    – ARi
    Dec 11, 2015 at 5:01

2 Answers 2

Reset to default
10
$\begingroup$

Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that

  • pseudorandom generators exist, and
  • secure one-way permutations exist.

In other words, assuming that these two conjectures are true, no $\mathsf{coNP}$-complete set is P-immune. As pointed out in the comments by Lance, this is implied by Theorem 4.4 of

(Kaveh has already shown that your question is equivalent to whether every $\mathsf{coNP}$-complete sets contains an infinite $\mathsf{P}$ subset. In other language, this is saying that no $\mathsf{coNP}$-complete set is "$\mathsf{P}$-immune." This is the language used in the above-referenced theorem.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ ECCC draft $\endgroup$
    – Kaveh
    Dec 9, 2015 at 20:57
  • $\begingroup$ By strong hard-core functions (and iteration), one-way permutations imply pseudorandom generators. ​ ​ $\endgroup$
    – user6973
    Dec 10, 2015 at 4:44
  • 1
    $\begingroup$ @RickyDemer: See Definitions 4.1-4.3 in the cited paper. If I'm understanding correctly, OWPs imply what they call "crypto-PRGs", but not necessarily what they call "PRGs" in the Glasser-Pavan-Selman-Sengupta paper. For their result, they (seem to) need both OWPs and what they call PRGs. $\endgroup$
    – Joshua Grochow
    Dec 10, 2015 at 5:45
  • 6
    $\begingroup$ Kaveh only showed the equivalence to co-NP-complete sets are P-immune, but the conclusion of theorem 4.4 in Glasser et al that all NP-complete sets must have length-increasing reduction, also implies that there are no co-NP-complete P-immune sets. $\endgroup$
    – Lance Fortnow
    Dec 10, 2015 at 13:28
  • $\begingroup$ @JoshuaGrochow Thanks...but are there assumptions we can make which in turn imply the non existence of such a language. I was more interested in scenarios where there is no poly time superset $\endgroup$
    – ARi
    Dec 26, 2015 at 12:38
5
$\begingroup$

Interesting question. The statement

for every NP-complete $L$, there is $U$ in P such that $L \subseteq U$ and $U^c$ is infinite.

is equivalent to:

for every NP-complete $L$, complement of $L$ contains an infinite P set.

which is in turn equivalent to

every coNP-complete set contains an infinite P set.

which is by symmetry the same as

every NP-complete set contains an infinite P-set.

I don't think the answer is known. I think natural NP-complete sets satisfy this condition easily. I don't think we have tools to build an artificial set which fails the statement. (see Lance's comment below)

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your initial statement is trivially true. ​ (Let U be the full language.) ​ ​ ​ ​ $\endgroup$
    – user6973
    Dec 9, 2015 at 20:10
  • $\begingroup$ Its an interesting chain of deductions...Could you give an example of a natural NP complete language in this regard $\endgroup$
    – ARi
    Dec 10, 2015 at 12:41
  • 3
    $\begingroup$ The symmetry doesn't make sense. For example, every c.e. set has an infinite computable subset but there are co-c.e.-sets that don't. $\endgroup$
    – Lance Fortnow
    Dec 10, 2015 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.