<p>I think both are NPI under the stronger assumption (but obviously true) that NP is not in "infinitely often P" - i.e., every polynomial time algorithm A and every sufficiently large n, A fails to solve SAT on inputs of length n.</p>

<p>In this case, such languages are not in P, but they also cannot be NP complete, since otherwise a reduction from SAT to a language L with large holes will give an algorithm for SAT that succeeds on these holes.</p>

<p>Such an assumption is also necessary, since otherwise the languages can be in P, or NP-complete, depending on where the "easy input lengths" are located.</p>

CC BY-SA 2.5
2010-09-22T06:39:06.330Z
@Boaz: I sort of understand what you mean by "such an assumption is necessary," but I'm having trouble formalizing the necessity.  I think one construct an oracle $X$, without too much difficulty, such that $P^X \neq NP^X$, there is a poly-time machine $M$ such that $M^X$ decides $SAT^X$ on infinitely many input lengths, yet $L_1^X$ and $L_2^X$ are $NP^X$-intermediate.
Joshua Grochow
CC BY-SA 2.5
2010-09-22T13:58:55.510Z
What I meant is that the assumption $NP\neq P$ is not sufficient on its own to show these languages are NP-intermediate, since we cannot rule out the case that $NP\neq P$ but there is an algorithm that solves SAT exactly on the inputs that $L_1$ is non-trivial, in which case $L_1$ would be in $P$ and $L_2$ would be NPC.
Boaz Barak
CC BY-SA 2.5
2010-09-22T15:11:44.477Z
@Boaz: Ah of course. One formalization of this is an oracle $X$ such that $P^X \neq NP^X$ but $L_1^X \in P$ (which I believe, similar to the other oracle I mentioned, is not too difficult to construct).  (PS - By using @name, it ensures that the other user is notified of your comment.)
Joshua Grochow
CC BY-SA 2.5
2010-09-24T21:28:59.470Z
@Joshua: If $L_1^X\in P$ let $M$ be a Poly-time machine for $L_1^X$, then $M$ would also solve $L_1$ since the case without query to oracle is just a special case. So if you can create a $X$ as you describe it you prove that $P_1\in P$ hence I really don't understand how you could do it.
Arthur MILCHIOR
CC BY-SA 2.5
2010-09-24T21:32:54.640Z
@Joshua: about your first comment under Boaz Barak, if $M\in P^X$ solve $SAT^X$ (on infinitely many input lengths) then I guess you want your $X$ at least to be an oracle for $SAT$. But since you can have query to $X$ in your formula #, then in fact you even need $X$ to be an oracle for $SAT^X$. How can you show that such a recursive definition is correct ? It doesn't seems clear at all to me. (#I guess that SAT^X is SAT where X can be also in the clauses)
Arthur MILCHIOR
CC BY-SA 2.5
2010-09-25T16:51:04.360Z
@Arthur: About your first comment, I meant to say "$L_1^X \in P^X$ rather than $L_1^X \in P$. In this case, although $M^X$ would indeed solve $L_1$, it might be using queries to $X$ to help. About your second comment: Since we only need $M^X$ to solve $SAT^X$ *only on infinitely many input lengths*, we do not in fact need (or want) $X$ to be an oracle for SAT. But it also seems to me that your question would apply to any oracle that makes $P = NP$, yet any PSPACE-complete set does the trick.
Joshua Grochow
CC BY-SA 2.5
2010-09-22T05:14:21.057Z
2010-09-22T05:14:21.057Z
Boaz Barak
<p>Assume $P \neq NP$</p>

<p>Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$).</p>

<p>|x| is the size of the instance x.</p>

<p>Let L be a language, $L|_{f(i)\leq |x| &lt; g(i)} := \{ x \in L \mbox{ |  } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| &lt; g(i) \}$</p>

<p>What is the complexity of the following languages :</p>

<p>$L_1 = SAT|_{{}^{2i}2 \leq |x| &lt; {}^{2i+1}2}$
$L_2 = SAT|_{{}^{2i+1}2 \leq |x| &lt; {}^{2i+2}2}$</p>

<p>As $L_1 \sqcup L_2 = SAT$, they can't be both in P under the assumption that $P \neq NP$.
As there both have exponential holes, I don't think SAT can be reduced to one.</p>

<p>Hence the intuition would be that they are both in NPI, but I can't find a proof or disproof.</p>

<p>Two others languages are
$L_3 = SAT|_{|x|={}^{2i+1}2}$
$L_4 = SAT|_{|x|={}^{2i}2}$</p>

<p>If one of both is in NPC, the other is in P because for each instance of one, it can't be transformed into an greater instance of the other because it is of exponential size, and smallers instances have a logarithmic size. Still by intuition, there is no reason why they would have a different complexity. What would their complexity be ?</p>

<p>Ladner's proof of NPI problems under $P \neq NP$ assumption use languages like $L_1$ or $L_2$, but $L_1$ and $L_2$ aren't built by diagonalization.</p>

CC BY-SA 3.0
2016-08-04T03:54:23.560Z
Is the assumption ""infinitely often P" formally stated anywhere where we can refer to?
Palash Dey
CC BY-SA 2.5
2010-09-21T21:28:33.977Z
Your languages have many instances that are padded by the addition of extra clauses that do not interact with each other.  They therefore seem NPI by Schöning's diagonalization argument?  http://dx.doi.org/10.1016/0304-3975(82)90114-1
András Salamon
CC BY-SA 2.5
2010-09-21T22:48:22.057Z
After "they can't be both in P", it should say "under the assumption that P $\ne$ NP..."
Emil
CC BY-SA 2.5
2010-09-21T23:05:58.237Z
I added "under the assumption" even if I already set this assumption before.
Ludovic Patey
CC BY-SA 2.5
2010-09-22T02:05:25.047Z
My guess is that the exponential holes in L1 and L2 are not sufficient to guarantee that they are provably not NP-complete.  I do not know how large the holes are in Ladner’s proof, but I suspect that they are larger than those of L1 and L2.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T02:34:53.917Z
If either L1 or L2 is NP-complete, then the Isomorphism Conjecture fails, since neither L1 nor L2 is a cylinder (has a padding function). So proving that one of them *is* NP-complete requires non-relativizing techniques. I don't yet see any barrier to showing that one of them is not NP-complete though.
Joshua Grochow
CC BY-SA 2.5
2010-09-22T14:39:33.153Z
But if we find an algorithm which solves one of them in polynomial time, then it proves that the other one is NP-complete. Hence if there is such an algorithm, does in mean that SAT isn't NP-complete under TM with an oracle such as the Isomorphism Conjecture works ?
Ludovic Patey
CC BY-SA 2.5
2010-09-22T15:08:03.067Z
Not quite.  $SAT^X$ is always $NP^X$-complete for any oracle $X$, since the proof of Cook-Levin relativizes.  Rather it means that finding a poly-time algorithm for either language requires non-relativizing techniques.  Formally: there is no poly-time oracle machine $M^X$ such that for *all* oracles $X$, $M^X$ solves at least one of $L_1^X$ and $L_2^X$.
Joshua Grochow
CC BY-SA 2.5
2010-09-22T21:15:37.047Z
I'm not sure to understand : a poly-time algorithm on a TM always relativizes as we just have not to use the oracle. Hence if there is no poly-time oracle machine $M^X$ such that for all oracles $X$ $M^X$ solves at least one of $L_1^X$ and $L_2^X$, this seems to prove there is no poly-time algorithm for TM without oracles, and then neither $L_1$ nor $L_2$ is in P. But this question isn't dependant from $L_1$ and $L_2$ : if we find a poly-time algorithm for SAT, as it relativizes, what about complexity classes where we have an oracle A such as P!= NP ?
Ludovic Patey
CC BY-SA 2.5
2010-09-23T01:23:12.567Z
I may have been a bit unclear with my quantifiers.  Let me add parentheses: there does not exist a poly-time oracle machine $M$ such that [for all $X$ [$M^X$ solves $L_1^X or L_2^X$]]. That is, for any $M$, it may be that for *some* X, $M^X$ solves one of the languages, but it cannot be true for all $X$. So, for example, $M$ without the oracle might solve $L_1$ (unrelativized), but no matter what $M$ is, there will be some oracle such that it does not solve either language.
Joshua Grochow
<cc.complexity-theory><np-hardness><complexity-classes>
What are the complexities of the following SAT subsets ?
Ludovic Patey
# What are the complexities of the following SAT subsets ?

(Asked by: username_0 on 2010-09-21)

Assume $P \neq NP$

Let use the following notation ${}^ia$ for tetration (ie. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}\_{i \mbox{ times}}$).

|x| is the size of the instance x.

Let L be a language, $L|\_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

What is the complexity of the following languages :

$L\_1 = SAT|\_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$
$L\_2 = SAT|\_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

As $L\_1 \sqcup L\_2 = SAT$, they can't be both in P under the assumption that $P \neq NP$.
As there both have exponential holes, I don't think SAT can be reduced to one.

Hence the intuition would be that they are both in NPI, but I can't find a proof or disproof.

Two others languages are
$L\_3 = SAT|\_{|x|={}^{2i+1}2}$
$L\_4 = SAT|\_{|x|={}^{2i}2}$

If one of both is in NPC, the other is in P because for each instance of one, it can't be transformed into an greater instance of the other because it is of exponential size, and smallers instances have a logarithmic size. Still by intuition, there is no reason why they would have a different complexity. What would their complexity be ?

Ladner's proof of NPI problems under $P \neq NP$ assumption use languages like $L\_1$ or $L\_2$, but $L\_1$ and $L\_2$ aren't built by diagonalization.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes

> **Comments:**
> **username_2**: Your languages have many instances that are padded by the addition of extra clauses that do not interact with each other.  They therefore seem NPI by Schöning's diagonalization argument?  http://dx.doi.org/10.1016/0304-3975(82)90114-1  
> **username_3**: After "they can't be both in P", it should say "under the assumption that P $\ne$ NP..."  
> **username_0**: I added "under the assumption" even if I already set this assumption before.  
> **username_4**: My guess is that the exponential holes in L1 and L2 are not sufficient to guarantee that they are provably not NP-complete.  I do not know how large the holes are in Ladner’s proof, but I suspect that they are larger than those of L1 and L2.  
> **username_5**: If either L1 or L2 is NP-complete, then the Isomorphism Conjecture fails, since neither L1 nor L2 is a cylinder (has a padding function). So proving that one of them *is* NP-complete requires non-relativizing techniques. I don't yet see any barrier to showing that one of them is not NP-complete though.  
> **username_0**: But if we find an algorithm which solves one of them in polynomial time, then it proves that the other one is NP-complete. Hence if there is such an algorithm, does in mean that SAT isn't NP-complete under TM with an oracle such as the Isomorphism Conjecture works ?  
> **username_5**: Not quite.  $SAT^X$ is always $NP^X$-complete for any oracle $X$, since the proof of Cook-Levin relativizes.  Rather it means that finding a poly-time algorithm for either language requires non-relativizing techniques.  Formally: there is no poly-time oracle machine $M^X$ such that for *all* oracles $X$, $M^X$ solves at least one of $L_1^X$ and $L_2^X$.  
> **username_0**: I'm not sure to understand : a poly-time algorithm on a TM always relativizes as we just have not to use the oracle. Hence if there is no poly-time oracle machine $M^X$ such that for all oracles $X$ $M^X$ solves at least one of $L_1^X$ and $L_2^X$, this seems to prove there is no poly-time algorithm for TM without oracles, and then neither $L_1$ nor $L_2$ is in P. But this question isn't dependant from $L_1$ and $L_2$ : if we find a poly-time algorithm for SAT, as it relativizes, what about complexity classes where we have an oracle A such as P!= NP ?  
> **username_5**: I may have been a bit unclear with my quantifiers.  Let me add parentheses: there does not exist a poly-time oracle machine $M$ such that [for all $X$ [$M^X$ solves $L_1^X or L_2^X$]]. That is, for any $M$, it may be that for *some* X, $M^X$ solves one of the languages, but it cannot be true for all $X$. So, for example, $M$ without the oracle might solve $L_1$ (unrelativized), but no matter what $M$ is, there will be some oracle such that it does not solve either language.  
> **username_1**: Is the assumption ""infinitely often P" formally stated anywhere where we can refer to?  

---

## 1 answers

### Answer by username_6 on 2010-09-22. Score: 6 | Accepted answer

I think both are NPI under the stronger assumption (but obviously true) that NP is not in "infinitely often P" - i.e., every polynomial time algorithm A and every sufficiently large n, A fails to solve SAT on inputs of length n.

In this case, such languages are not in P, but they also cannot be NP complete, since otherwise a reduction from SAT to a language L with large holes will give an algorithm for SAT that succeeds on these holes.

Such an assumption is also necessary, since otherwise the languages can be in P, or NP-complete, depending on where the "easy input lengths" are located.

> **Comments:**
> **username_5**: @Boaz: I sort of understand what you mean by "such an assumption is necessary," but I'm having trouble formalizing the necessity.  I think one construct an oracle $X$, without too much difficulty, such that $P^X \neq NP^X$, there is a poly-time machine $M$ such that $M^X$ decides $SAT^X$ on infinitely many input lengths, yet $L_1^X$ and $L_2^X$ are $NP^X$-intermediate.  
> **username_6**: What I meant is that the assumption $NP\neq P$ is not sufficient on its own to show these languages are NP-intermediate, since we cannot rule out the case that $NP\neq P$ but there is an algorithm that solves SAT exactly on the inputs that $L_1$ is non-trivial, in which case $L_1$ would be in $P$ and $L_2$ would be NPC.  
> **username_5**: @Boaz: Ah of course. One formalization of this is an oracle $X$ such that $P^X \neq NP^X$ but $L_1^X \in P$ (which I believe, similar to the other oracle I mentioned, is not too difficult to construct).  (PS - By using @name, it ensures that the other user is notified of your comment.)  
> **username_7**: @Joshua: If $L_1^X\in P$ let $M$ be a Poly-time machine for $L_1^X$, then $M$ would also solve $L_1$ since the case without query to oracle is just a special case. So if you can create a $X$ as you describe it you prove that $P_1\in P$ hence I really don't understand how you could do it.  
> **username_7**: @Joshua: about your first comment under username_6, if $M\in P^X$ solve $SAT^X$ (on infinitely many input lengths) then I guess you want your $X$ at least to be an oracle for $SAT$. But since you can have query to $X$ in your formula #, then in fact you even need $X$ to be an oracle for $SAT^X$. How can you show that such a recursive definition is correct ? It doesn't seems clear at all to me. (#I guess that SAT^X is SAT where X can be also in the clauses)  
> **username_5**: @Arthur: About your first comment, I meant to say "$L_1^X \in P^X$ rather than $L_1^X \in P$. In this case, although $M^X$ would indeed solve $L_1$, it might be using queries to $X$ to help. About your second comment: Since we only need $M^X$ to solve $SAT^X$ *only on infinitely many input lengths*, we do not in fact need (or want) $X$ to be an oracle for SAT. But it also seems to me that your question would apply to any oracle that makes $P = NP$, yet any PSPACE-complete set does the trick.  

---

