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

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?