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?

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

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Gere
    Commented Jun 7, 2022 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
    Commented Jun 7, 2022 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.