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}$.

  • 1
    If this is a research-level question, you can try asking it at [CSTheory](http://cstheory.stackexchange.com).2011-02-26
  • 1
    I am _no_ researcher and therefore I am only privately interested in this question.2011-02-26
  • 4
    1) You don't have to be a researcher to ask research-level questions. 2) If you know that the problem is equivalent to P vs. NP, why bother asking it?2011-02-26
  • 2
    If your question is equivalent to "Does anyone know how to solve P $\neq$ NP?", then the answer is certainly "no". If you cross-post this question to CSTheory, it may not be well-received. If you re-phrase your question to something like "Are there known barriers to this approach to P $\neq$ NP?", this might be better. However, you'll need to be much more explicit in your approach.2011-02-26
  • 0
    Dear Yuan, meanwhile I asked it at CSTheory. With my above question, I wanted only to share my main idea for attacking this problem. Perhaps some experienced mathematician like you is able to use my idea in some way.2011-02-26
  • 0
    @mhum: Thanks for helping me to express my proper question better.2011-02-26
  • 1
    @Steffen: You should first present a plan of attack for this particular theorem, in other words, an outline of a proof, and only then can we answer your question.2011-02-26
  • 0
    There are well-known [barriers](http://cstheory.stackexchange.com/questions/5162/are-there-any-known-barriers-to-use-some-approach-for-solving-p-vs-np) as the researcher Ph.D. Tsuyoshi Ito from the University of Waterloo told, so my approach will very likely not work.2011-02-26
  • 1
    The question is which of them apply to your case, for example, will your proof relativize? That may depend either on the general approach (which you've outlined) or on the particular "proof strategy", and in the latter case Tsuyoshi's general answer isn't very helpful; people are trying to avoid the barriers, so the correct question is "does this approach avoid the barriers?", since otherwise it is hopeless.2011-02-26
  • 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
    @Tsuyoshi: Thank you very much for your answer.2011-02-27
  • 0
    For the last statement of Tsuyoshi I humbly refer the math.se community to the ongoing [discussion](http://cstheory.stackexchange.com/questions/5162/are-there-any-known-barriers-to-use-some-approach-for-solving-p-vs-np) in cstheory.2011-02-27
  • 0
    @Steffen: Perhaps you can edit the question to add your comments, in reference to Tsuyoshi's answer, rather than edit Tsuyoshi's answer directly.2011-02-28
  • 0
    @Arturo: All revisions to this answer so far were made by me, and “you” in the added part refers to Steffen. My apologies if it was not clear.2011-02-28
  • 0
    @Tsuyoshi: Steffen submitted an edit to this answer in which he added a bunch of stuff (labeled as "added by Steffen"), and which I rejected; he doesn't have enough reputation to make the edits himself. Sorry *I* didn't make that clear.2011-02-28
  • 0
    @Arturo: Ah, I see. Thank you for the explanation.2011-02-28
  • 0
    @Tsuyoshi: I added an answer to your question, appended to my question.2011-02-28
  • 1
    @Steffen: (1) In the meanwhile, I learned that NP ⊈ P-close is indeed equivalent to P≠NP. See my updated answer. (2) I read your addendum to the question. I do not think that I followed everything, but I think that it fails because both $C$ and $\bar{C}$ can be satisfiable at the same time.2011-02-28
  • 0
    @Tsuyoshi: Thank you very much. You noted indeed the essential error in my construction. I appreciate your help very highly.2011-02-28
  • 0
    @Tsuyoshi: The propositions and proofs in your answer are clearly correct and using the result of Ogihara and Watanabe they are also elegant. Again thanks a lot for your competent work.2011-03-01
  • 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