# 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.  below does not directly address this.

Here is my proof attempt:

 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

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

 From  and  (P = NP).

 (P = NP) implies (P-complete = NP-complete).

 From  and  (P-complete = NP-complete).

 From  and  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

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

 From  and  (L = P).

 From  and  (L = NP).

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

Your claim  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.