# 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 ⛌.

**Turing machine halting problem.**

*Example:-***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