Algorithm problems category
1) Unsolvable problem: No problems exist to solve them
2) Solvable problem: An algorithm exists to solve them. There is a systematic procedure that can provide a correct solution for any instance of the problem
Polynomial problem(P): Class of solvable problems for which there exists an algorithm that can solve them in polynomial time
-Nondeterministic Polynomial problem(NP):
-Polynomial time means that the running time of the algorithm is bounded by a polynomial function of the input size.
-Class of solvable problems for which a potential solution can be verified in polynomial time.
Nondeterministic polynomial time problem (NP):
Class of solvable problems for which a potential solution can be verified in polynomial time.
-If someone claims to have a solution to an NP problem, it can be verified in polynomial time. However, finding the solution itself is not guaranteed to be efficient.
R:Problems solvable in finite time
-Class of problems that are decidable in finite time. There exists an algorithm that can determine the answer in a finite number of steps.
Set of problems that have an algorithmic solution with a guaranteed termination.
EXP: Problems solvable in exponential time 2^n
-Specifically in time 2^n for some positive constant. The running time of the algorithm grows exponentially with the input size.
The complexity class EXP includes problems that can be solved in a time complexity that is worse than polynomial time (P)
P (Polynomial Time):Running time is bounded by a polynomial function of the input size.
Ex.If the input size is represented by ‘n’, a polynomial time algorithm would have a running time of O(n^k) for some constant ‘k’.
Polynomial time problems are considered efficient because the running time grows at a reasonable rate as the input size increases.
P <- Exp <- R