Complexity Classes

Problem types:

1. Decision Problems: Given an input \(x\) output \(\{0, 1\}\) i.e. the input it either accepted to rejected, or in other words the input is valid instance of the problem or not..

2. Relational Problesm: Given an input \(x\) output a \(y\) such that \((x, y) \in R \subseteq \{0,1\}^* \times \{0,1\}^*\)

   The \(y\) is sometimes called the "witness" to the original decision problem. So, instead of just determining that a solution exist, relational problem give the solution too.

   Decision problem are a subset of Relational problem.

   Relational Problem are also called Functional Problem because it looks like a function \(y=f(x)\).

3. Optimization Problem: A subclass of Relational Problem where the objective is to find an optimal value. Its not that different from relational problem just that conceptually we are looking it as an optimization problem. Optimization problem are subclass of Relational problem.

Complexity Class:

P

Decision problem that can be solved in polynomial time.

PO

Optimization problem that can be solved in polynomial time.

FP

Functional/Relation problem that can be solved in polynomial time.

FP generalizes PO and P.

PSPACE

Decision problem that can be solved in polynomial space with no restriction in time.

BPP

Bounded-error Probabilistic Polynomial - Decision problem solved in polynomial time with error probability \(\leq 1/3\).

It is suggested that BPP = P, but there is no proof.

BQP

Bounded-error Quantum Polynomial - Decision problem solved by quantum computer in polynomial time with error probability \(\leq 1/3\).

If PSPACE = P, then BQP = P. But it is believed that BQP > P.

NP

Decision problem for which a polynomial sized proof/witness can verify in polynomial time that the input \(x\) is a valid.

NPO

NP Optimization

FNP

Functional NP - Relation problem for which polynomial sized proof can be verified in polynomial time to be the solution.

FNP > NPO

NP-Complete

A NP problem, to which all problems in NP can be converted into in polynomial time.

NP-Hard

Problem inside or outside of NP which is as difficult as NP-complete.

NP-Hard > NP-Complete

QMA

Quantum Merlin-Arthur - Decision problem which can be verified with in quantum computer in polynomial time using quantum state with polynomial number of qubits as the proof.

QMA-Complete

Quantum equivalent of NP-Complete.

QMA-Hard

Quantum equivalent of NP-Hard.

Examples:

• Travelling salesman problem
  1. Decision problem is NP-complete
  2. Relational Problem is \(FP^{NP}\) -complete i.e. it can be completed in polynomial time if given access to an NP oracle.