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 x∈L and decide (by invoking the oracle for S) whether x∈S, 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