8
$\begingroup$

Are there any known barriers to show the following invariant (perhaps by some sort of induction)?

Let $\Sigma$ be some finite alphabet with $|\Sigma| \geq 2$, let $M$ be some (deciding) deterministic Turing machine with input alphabet $\Sigma$, and let $L_0 \subseteq \Sigma^{\star}$ be some non-sparse, $\mbox{NP}$-complete language.
Then at least one of the following properties hold:

  1. $M$ doesn't terminate always.
  2. $M$ has superpolynomial time complexity.
  3. $L(M) \triangle L_0$ is non-sparse.

Concise problem description: $\mbox{NP} \not\subseteq \mbox{P-close}$ (according to Tsuyoshi Ito, see his answer).

Caution: This problem is equivalent to $\mbox{P} \neq \mbox{NP}$.

  • 0
    @Yuval: Thanks a lot for explaining so much to me. I'll try to study those barriers during the next time. If I should arrive at some usable result, I will inform you and the other interested people from math.se about it. The usual barriers seem to be relativization, natural proof and algebraic ones.2011-02-26

1 Answers 1

7

This is a slightly more detailed version of some of my comments on your cross-posting on cstheory.stackexchange.com.

The statement which you described can be concisely written as NP ⊈ P-close. Here P-close is the class of decision problems for which there exists a polynomial-time algorithm A such that the set of instances on which A fails to answer correctly is sparse.

It is easy to see that P ⊆ P-close ⊆ P/poly, from which it is easy to see the implications hold that NP ⊈ P/poly ⇒ NP ⊈ P-close ⇒ P≠NP. Since NP ⊈ P-close implies P≠NP, any proof of NP ⊈ P-close must also overcome the relativization barrier and the algebrization barrier. I do not know if the natural-proof barrier (which every proof of NP ⊈ P/poly must overcome) necessarily applies to NP ⊈ P-close.

I do not think that it is known that NP ⊈ P-close is equivalent to P≠NP as you claim.


Edit: On the contrary to what I wrote in an earlier revision, I learned that NP ⊈ P-close is indeed equivalent to P≠NP. Although I already answered your question about barriers above, I guess that writing down the proof of this equivalence may be useful. The proof is based on what you described on cstheory.stackexchage.com with one modification (namely, I use the result by Ogihara and Watanabe instead of Mahaney’s theorem).

As stated above, we have the implication NP ⊈ P-close ⇒ P≠NP. We will prove the converse: NP ⊆ P-close ⇒ P=NP.

A polynomial-time k-truth-table reduction from a language L1 to a language L2 is a Turing reduction from L1 to L2 which invokes the oracle at most k times nonadaptively. Note that a many-one reduction is a special case of a 1-truth-table reduction. Ogihara and Watanabe [OW91] proved the following result:

Theorem [OW91]. If some sparse language is NP-complete under polynomial-time k-truth-table reducibility for some constant k, then P=NP.

Note that this theorem generalizes Mahaney’s theorem, which is the special case of the theorem where the reduction is restricted to a polynomial-time many-one reduction.

Assume NP ⊆ P-close. Then SAT ∈ P-close. Equivalently, there exists a language L∈P such that the symmetric difference S=SAT△L is sparse. Then the following is a polynomial-time 1-truth-table reduction from SAT to S: given an input x, decide (in polynomial time) whether xL and decide (by invoking the oracle for S) whether xS, and return the XOR of the two results. Therefore, the sparse set S is NP-complete under polynomial-time 1-truth-table reducibility. This implies P=NP by the aforementioned theorem by Ogihara and Watanabe.

[OW91] Mitsunori Ogihara and Osamu Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471–483, June 1991. http://dx.doi.org/10.1137/0220030

  • 0
    @Steffen: You’re welcome. By the way, I knew that you were convinced by my proof in the previous revision (revision 5). The reason I revised the proof to revision 6 is that after rereading revision 5, I did not like my own way of writing the proof. There is nothing wrong for you to have replied, but you do not _have to_ give a response to every edit of the answer!2011-03-01