0
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$ Jun 7 at 7:55
  • $\begingroup$ Not sure I understand. Isn't there always a harder problem to any polynomial time problem? $\endgroup$
    – Gerenuk
    Jun 7 at 7:58
  • $\begingroup$ Yes, but why should that matter ? $\endgroup$ Jun 7 at 8:02
  • $\begingroup$ Because you cannot find a hardest problem, which however does exist if P=NP $\endgroup$
    – Gerenuk
    Jun 7 at 8:03
  • $\begingroup$ What you say is quite confuse, sorry. $\endgroup$ Jun 7 at 8:14

2 Answers 2

1
$\begingroup$

If a problem X is NP-complete, that means "I can solve any problem in NP by converting it into an instance of X that has the same YES or NO answer in polynomial time, and solving that instance.". We are very, very generous with "polynomial" factors here. n^2 and n^1000 are considered equal in this context, because it's just polynomial.

So with this background, if P = NP were true, then all problems in P would indeed be considered to be equally hard because we don't care about polynomial factors in this context.

$\endgroup$
2
  • $\begingroup$ But you cannot just say all P problems are equally hard? I suppose there is a well-defined notion that they are comparable and not equal? Or is this notion different for the definition of NP complete? $\endgroup$
    – Gerenuk
    Jun 7 at 8:43
  • $\begingroup$ In the context of P vs. NP, yes, you can absolutely claim they are equally hard. Because tiny differences like polynomials are ignored in this situation. $\endgroup$
    – gnasher729
    Jun 7 at 10:56
0
$\begingroup$

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

$\endgroup$

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.