pratap singh, upendra
pratap singh, upendra
Branch Unspecified
01 Nov 2015

Classification of a problem: - does it requires algorithm also

Hi,

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?

Be the first one to reply

Share this content on your social channels -

Only logged in users can reply.