View Feed
Coffee Room
Discuss anything here - everything that you wish to discuss with fellow engineers.
12915 Members
Join this group to post and comment.

Classification of a problem: - does it requires algorithm also


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 the time complexity of the algorithm used to solve the problem.

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

  1. A1 is polynomial in nature,
  2. A2 is non-polynomial and
  3. A3 has 'other' run-time characteristics different from A1 and A2.
According to me,
If P is solved using A1, then P is a Polynomial problem.
If P is solved using A2, then it becomes NP problem and if P is solved using A3 then it must be of a type different from Polynomial or Non-Polynomial problem.

Am I right?

In other words, is it fair enough to say that classification of a problem does also require the algorithm as an input?

Share this content on your social channels -