# complexity theory – Clarifying the definition of reduction with regards to NP-complete problems

A problem $$L$$ is $$text{NP}$$-complete if $$L$$ is in $$text{NP}$$, and $$L$$ is $$text{NP}$$-hard (that is, $$Kleq_p L$$ for all $$Kin text{NP}$$ ). Consider the following claims.

Claim 1: if $$L$$ is $$text{NP}$$-complete and $$Lin text{P}$$, then $$text{NP} subseteq text{P}$$ (that is, all problems in $$text{NP}$$ can be solved in deterministic polynomial time).

Claim 2: If $$A leq_p B$$, then $$Bin text{P} to A in text{P}$$.

What you asked about is claim 1. To begin with, its correctness follows from claim 2. Indeed, if $$L$$ is $$text{NP}$$-complete, then for every $$Ain text{NP}$$, it holds that $$Aleq_p L$$. Thus, if we assume that $$Lin text{P}$$, then we get by claim 2 that $$Ain text{P}$$, and therefore $$text{NP} subseteq text{P}$$. So what is missing for you is the proof of claim 2, and a sketch of its proof goes as follows. If $$M_f$$ is a TM that computes a polynomial time reduction from $$A$$ to $$B$$, and $$M_B$$ is a TM that decides $$B$$ in polynomial time, then a TM $$M_A$$ that decides $$A$$ in polynomial time operates as follows. On input $$x$$, $$M_A$$ computes $$y = M_f(x)$$, then $$M_A$$ runs $$M_B$$ on $$y$$, and answers the same. What is left to show is that $$M_A$$ decides $$A$$ in polynomial time, and I leave that to you (use the fact that |y| is polynomial, and a composition of polynomials is a polynomial).