10
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ 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 $\endgroup$
    – András Salamon
    Sep 21, 2010 at 21:28
  • $\begingroup$ After "they can't be both in P", it should say "under the assumption that P $\ne$ NP..." $\endgroup$
    – Emil
    Sep 21, 2010 at 22:48
  • $\begingroup$ I added "under the assumption" even if I already set this assumption before. $\endgroup$
    – Ludovic Patey
    Sep 21, 2010 at 23:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Sep 22, 2010 at 2:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Sep 23, 2010 at 1:23

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Sep 22, 2010 at 6:39
  • $\begingroup$ 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. $\endgroup$
    – Boaz Barak
    Sep 22, 2010 at 13:58
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Joshua Grochow
    Sep 22, 2010 at 15:11
  • $\begingroup$ @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. $\endgroup$
    – Arthur MILCHIOR
    Sep 24, 2010 at 21:28
  • $\begingroup$ @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) $\endgroup$
    – Arthur MILCHIOR
    Sep 24, 2010 at 21:32

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.