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?

Replies

You are reading an archived discussion.

Related Posts

Lot of engineering students are concerned about ways to find a good job when the college offers no campus placements. India produces upwards of 7 lakh engineers every year and...
Bharat Sanchar Nigam Limited (BSNL) is collaborating with Social Media King - Facebook to set up 100 Wi-Fi hotspots in various rural areas in southern and western India. Interestingly, a...
Coming from a Sindhi business family, Manisha Raisinghani always felt it that entrepreneurship was always in her blood. Her family urged her to seek out challenges and to pave her...
many have tried it before, but failed..... i want to privatise world's technological advancement....... (UNDER ME OF COURSE) you would now be thinking ,may be i am little hittler-ish ,well...
Artificial cardiac pacemakers that have been a boon to the lives of millions for more than half a century are getting a wonderful makeover with a group of researchers from...