Complexity Classes: P, NP, NPH and NPC
COMPLEXITY THEORY
Computational theory is mainly used to recognize whether the problem that is decidable is easy or hard. This can be calculated by means of time complexity and space complexity.
Complexity Classes
P-space Problem
The language in P-space represents the polynomial space complexity of the language.
NP-space Problem
The language in NP space represents the non polynomial space complexity of the language.
P-problem
P is the class of problems that can be solved by deterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
It consists of all language accepted by some deterministic turing machine that runs in polynomial amount of time, as a function of input length.
Example:-
1-SAT
2-SAT
Unary partition
Shortest path
2-colourability
Eular cycle
Equivalence of DFA
Min cut
Shortest cycle in a graph
Sorting
NP-problem
NP is the class of problems that can be solved by nondeterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
It consists of all languages that are accepted by non deterministic turing machines with a polynomial bound on the time taken along any sequence of non deterministic choices.
Example:-
1. Traveling sales person problem and
2. Sub graph isomorphism.
NP-Hard Problem
If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and we cannot prove that ⛌ is in NP then ⛌ is said to be NP-Hard problem.
A problem ⛌ is NPH iff ∀ Y ∈ NP , Y ≤p ⛌.
Example:- Turing machine halting problem.
NP-Complete Problem
If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and ⛌ is in NP then ⛌ is said to be NP-Hard problem.If NP hard problem is present in NP then it is called NP-complete problem.
A problem ⛌ is NPC iff ∀ Y ∈ NP, Y ≤p ⛌ ⛌∈ NP
Example:-
3-SAT
Traveling sales man problem
Hamilton circuit problem
Vertex cover problem
Independent set problem
Chromatic number problem
Coloring problem
Sub-graph isomorphism problem
Edge cove problem
Knapsack problem
Max cut
REDUCTION
P1 ≤ P2: Problem P1 is reducible to a problem P2. It means problem P2 is at-least as hard as problem P1.
If P1 ≤ P2 and P1 is undecidable then P2 is also undecidable.
If P1 ≤ P2 and P2 is decidable then P1 is also decidable.
If P1 ≤ P2 and P2 is recursive then P1 is also recursive.
If P1 ≤ P2 and P2 is recursive enumerable then P1 is also recursive enumerable.
If P1 ≤ P2 and P2 is P-problem then P1 is also P-problem.
If P1 ≤ P2 and P2 is NP-problem then P1 is also NP-problem.
If NP-complete is in P then P=NP.
Computational theory is mainly used to recognize whether the problem that is decidable is easy or hard. This can be calculated by means of time complexity and space complexity.
Complexity Classes
P-space Problem
The language in P-space represents the polynomial space complexity of the language.
NP-space Problem
The language in NP space represents the non polynomial space complexity of the language.
P-problem
P is the class of problems that can be solved by deterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
It consists of all language accepted by some deterministic turing machine that runs in polynomial amount of time, as a function of input length.
Example:-
1-SAT
2-SAT
Unary partition
Shortest path
2-colourability
Eular cycle
Equivalence of DFA
Min cut
Shortest cycle in a graph
Sorting
NP-problem
NP is the class of problems that can be solved by nondeterministic algorithms in a time that is polynomially related to the size of the respective problem instance.
It consists of all languages that are accepted by non deterministic turing machines with a polynomial bound on the time taken along any sequence of non deterministic choices.
Example:-
1. Traveling sales person problem and
2. Sub graph isomorphism.
NP-Hard Problem
If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and we cannot prove that ⛌ is in NP then ⛌ is said to be NP-Hard problem.
A problem ⛌ is NPH iff ∀ Y ∈ NP , Y ≤p ⛌.
Example:- Turing machine halting problem.
NP-Complete Problem
If there is a language ⛌ such that every language Y in NP can be polynomially reducible to ⛌ and ⛌ is in NP then ⛌ is said to be NP-Hard problem.If NP hard problem is present in NP then it is called NP-complete problem.
A problem ⛌ is NPC iff ∀ Y ∈ NP, Y ≤p ⛌ ⛌∈ NP
Example:-
3-SAT
Traveling sales man problem
Hamilton circuit problem
Vertex cover problem
Independent set problem
Chromatic number problem
Coloring problem
Sub-graph isomorphism problem
Edge cove problem
Knapsack problem
Max cut
REDUCTION
P1 ≤ P2: Problem P1 is reducible to a problem P2. It means problem P2 is at-least as hard as problem P1.
If P1 ≤ P2 and P1 is undecidable then P2 is also undecidable.
If P1 ≤ P2 and P2 is decidable then P1 is also decidable.
If P1 ≤ P2 and P2 is recursive then P1 is also recursive.
If P1 ≤ P2 and P2 is recursive enumerable then P1 is also recursive enumerable.
If P1 ≤ P2 and P2 is P-problem then P1 is also P-problem.
If P1 ≤ P2 and P2 is NP-problem then P1 is also NP-problem.
If NP-complete is in P then P=NP.
No comments