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

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).

• I don’t see any question here. Apr 16, 2020 at 22:35
• @YuvalFilmus I added a question to the body Apr 17, 2020 at 3:01

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.