# How could NP-complete problems be in P?

I've learned some basics about P and NP. Please excuse if the following is not very precise.

I've read that NP-complete problems are the hardest problems in NP. (Is that correct?)

But now I'm wondering if P problems have polynomial runtime, and assuming P=NP for a moment, how can polynomial runtime problems ever have something like a "hardest problem"? How could polynomial runtime problems have a thing like the largest element?

EDIT: I just remembered that the notion of NP-complete being the "hardest" is defined up to polynomial transformations? And the comparability of P problems is a different thing. Is that the answer? Or can the notion of comparing P problems and NP-complete problems being the hardest be made similar?

• You are not considering a polynomial that bounds the complexity of all problems in the class, you are considering the class of all problems that can be solved in polynomial time (i.e. every problem has its own polynomial bound). Jun 7 at 7:55
• Not sure I understand. Isn't there always a harder problem to any polynomial time problem? Jun 7 at 7:58
• Yes, but why should that matter ? Jun 7 at 8:02
• Because you cannot find a hardest problem, which however does exist if P=NP Jun 7 at 8:03
• What you say is quite confuse, sorry. Jun 7 at 8:14

$$NP$$-complete problems are the hardest problems in $$NP$$ with regard to the time required to solve them. Despite more than 50 years of research, nobody was able to design a polynomial time algorithm to solve one of them (nor to prove a supra-polynomial lower bound either). Actually, solving one of them in polynomial time also implies solving them all and all of the problems in $$NP$$ through the concept of reduction. In practice, that will imply $$P = NP$$.
Now, if $$P = NP$$, then $$NP$$-complete problems are obviously easy (by definition of $$P$$) with regard to the time required to solve them.