P

• Solvable in polynomial time.
• Verifiable in polynomial time.
• Tractable problems
• Mentioned in Cobham's thesis (although not under this name).
• A problem is in P, then its complement is also in P.

NP

• No polynomial time solution
• NP stands for 'Non-deterministic Polynomial acceptable problems' (Source)
• Verifiable in polynomial time.
• Example: 3-SAT

Unsolved problem: Is P = NP ?

NP-Complete

• Like 'Hardest problems in NP' (but still got to be NP, unlike in the case of NP-Hard)

• All NP problems can be reduced to an NP-C problem in polynomial time.

• If a polynomial time solution was found to an NP-C problem, we can conclude that P = NP

• Example: Circuit satisfiability

  NP-C ⊂ NP

co-NP

• A problem is in co-NP if its complement is in NP.
• Therefore, the complement of every NP problem is co-NP.

Unsolved problem: Is NP = Co-NP ?

NP vs co-NP:

• A problem can be both NP and co-NP (eg: Primality)
• NP => A positive solution can be verified in P time
• co-NP => A negative solution can be refuted in P time
• Primality:
  • Proof of primality can be checked in P-time (Eg: AKS)
  • Compositeness proof of a number is prime factors => Can be checked in P-time

co-NP-Complete

• A problem is in co-NP-C if its complement is in NP-C.
• Therefore, the complement of every NP-C problem is co-NP-C.

NP-Hard

• Like 'at least as hard as the hardest problems in NP'.
• May not be even be NP.
• May not be even be decidable.
• Example: Subset sum problem

NP-Easy

• Like 'at most as hard as NP', but not necessarily in NP.

PSPACE

• Requires only polynomial memory space
• A problem is in PSPACE, then its complement is also in PSPACE.

Amount of space required is polynomial in the input size.

In polynomial time, an algorithm can only use polynomial amount of space. ie,

P ⊆ PSPACE

There is a PSPACE solution to 3-SAT problem. Consequently,

NP ⊆ PSPACE

Not proven that P ≠ PSPACE though that seems likely.

PSPACE Complete

• Any problem in PSPACE can be converted into this in polynomial time.
• Considered the hardest problems in PSPACE as a solution to a PSPACE Complete problem can be used to solve any PSPACE problem.
• Suspected to be outside P and NP, but not proven.

NC

• Nick's Class
• For parallel algorithms.
• Can be solved in 𝑂𝑙𝑜𝑔ᶜn) time using 𝑂(nᵏ) parallel processors for some c, k
• NC ⊂ PSPACE (from [space hierarchy theorem](https://en.wikipedia.org/wiki/Space_hierarchy_theorem))

Polylgorithmic time

Time is in O(logᵏn) which is same as O((log n)ᵏ)

Reducing a problem to another

Even when it is possible to reduce a problem X another problem Y in polynomial time, it may not be possible to reduce Y back to X.

For example, any computation problem can be converted to the halting problem (where the Turing halts for the output), but the halting problem cannot be converted to the computation problem (for the cases where the Turing machine doesn't halt). (A discussion)

Complement of a problem

Certificate of complexity

A solution path in within a verification process.