# What are the complexities of the following SAT subsets ?

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.

• 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? dx.doi.org/10.1016/0304-3975(82)90114-1 Sep 21 '10 at 21:28
• After "they can't be both in P", it should say "under the assumption that P $\ne$ NP..."
– Emil
Sep 21 '10 at 22:48
• I added "under the assumption" even if I already set this assumption before. Sep 21 '10 at 23:05
• 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. Sep 22 '10 at 2:34
• 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. Sep 23 '10 at 1:23

• @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. Sep 22 '10 at 6:39
• 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. Sep 22 '10 at 13:58
• @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.) Sep 22 '10 at 15:11
• @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. Sep 24 '10 at 21:28
• @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) Sep 24 '10 at 21:32