This question already has an answer here:

Just learnt that a problem in computer science can be divided into the following categories

Polynomial problems
NP problems
NP hard problems
NP complete problems

based on how long it takes to run the program

For example, suppose there is a problem P that can be solved with two algorithms say A1 and A2 where,

A1 is polynomial in nature,
A2 is non-polynomial

According to me, if P is solved using A1, then P is a polynomial problem and if P is solved using A2, then it must be an NP problem.

Am I right?

In other words, is it fair enough to say that classification of a problem does also require the algorithm that is being used to solve it?


marked as duplicate by Raphael Nov 1 '15 at 18:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ possible dup of cs.stackexchange.com/q/9556/755 $\endgroup$ – D.W. Nov 1 '15 at 18:38
  • $\begingroup$ Definitely a duplicate (cc @D.W.). Your question is answered by the definitions of the terms you use (without, apparently, really understanding what they mean). The reference question has wonderful answers that help you gain this understanding. $\endgroup$ – Raphael Nov 1 '15 at 18:50

No. The classification of problems into complexity classes is based on the amount of resources required to solve the problem, not the resources that some programmer decides to use. If you have a smart algorithm that solves a problem in polynomial time, and a dumb one that uses exponential time, the problem itself is in polynomial time because it can be solved within that resource bound.


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