2
$\begingroup$

Would a sparse NP-Complete language imply L = NP?

Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-complete to L-complete for NP=L. [4] below does not directly address this.

Here is my proof attempt:

[1] Assume there exists a (sparse NP-Complete language).

Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP.

https://en.wikipedia.org/wiki/Mahaney%27s_theorem

[2] In other words, (sparse NP-Complete language) implies (P = NP).

[3] From [1] and [2] (P = NP).

[4] (P = NP) implies (P-complete = NP-complete).

[5] From [3] and [4] (P-complete = NP-complete).

[6] From [1] and [5] there exists a (sparse P-Complete language)

In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse P-complete problem, then L = P."

https://en.wikipedia.org/wiki/Sparse_language

[7] In other words, (sparse P-complete problem) implies (L = P).

[8] From [6] and [7] (L = P).

[9] From [3] and [8] (L = NP).

$\endgroup$
  • $\begingroup$ I don’t see any question here. $\endgroup$ – Yuval Filmus Apr 16 at 22:35
  • $\begingroup$ @YuvalFilmus I added a question to the body $\endgroup$ – Jared Apr 17 at 3:01
5
$\begingroup$

Your claim [4] is wrong - the issue is with the term "$X$-complete" for a complexity class $X$.

Stricly speaking, barring specific convention the phrase "$X$-completeness" doesn't pin down a single notion: we also need to specify the reducibility notion involved. For example, Cai/Sivakumar look at P-completeness with respect to logspace and NC many-one reductions, while "NP-complete" refers to polynomial-time many-one reductions. Changing the reducibility notion changes the completeness (and hardness) notion - for a silly example, everything in P is NP-complete with respect to exponential-time Turing reductions.

So the implication "P=NP implies P-complete=NP-complete" is a non-sequitur, since the implicit reducibility notions are different. P=NP does imply (say) "P-complete w/r/t logspace reductions = NP-complete w/r/t logspace reductions," but that's a completely different thing.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sure, you would need a log-space reduction to prove L=P, for example? Wouldn't P=NP imply a polynomial time reduction from a NP-complete problem to a P-complete problem? $\endgroup$ – Jared Apr 17 at 2:58
  • $\begingroup$ I thought X-complete means "all problems in X can be reduced to X using X's (time and space) resources" where "using X's resources" is the "reproducibility notion". In this case, if P=NP, then any problem in NP could be reduced to a P-complete problem using polynomial time (and thus polynomial space if we're being precise) $\endgroup$ – Jared Apr 17 at 3:00
  • $\begingroup$ @WordsLikeJared "Wouldn't P=NP imply a polynomial time reduction from a NP-complete problem to a P-complete problem? " Yes (that's the definition - and "P-complete" can just be replaced with "any problem in P"), but I don't see how that's relevant. "I thought X-complete means "all problems in X can be reduced to X using X's (time and space) resources" where "using X's resources" is the "reproducibility notion"." No, it doesn't. E.g. we can talk about something being EXPTIME-complete with respect to polynomial-time many-one reductions. $\endgroup$ – Noah Schweber Apr 17 at 3:01
  • 2
    $\begingroup$ Sorry I was blind. I see now. Logspace reduction for P-complete. Didn't realize that. Thank you for your patience!!! $\endgroup$ – Jared Apr 17 at 3:08
  • $\begingroup$ @WordsLikeJared All good, this stuff's tricky at first (or at least it was for me). Glad I could help! $\endgroup$ – Noah Schweber Apr 17 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.