# Complexity Notes

Published on the## Introduction

- Turing machines can be time-bounded, by some function of its input, \(T(n)\), where \(n\) is the input length. This means it halts within \(T(n)\) steps.
- If a non-deterministic Turing machine is bounded by \(T(n)\), this means that the number of steps in any branch halts within \(T(n)\) steps.
- A decision problem is a problem with a yes or no answer for some input. A Turing machine for a decision problem accepts its input to indicate a “yes” answer and halts without accepting to indicate a “no” answer.
- Formally speaking, a decision problem is a function \(f(n)\), where \(f : \mathbb{N} \to \{0, 1\}\).
- Languages are isomorphic to decision problems; if the answer for some input to a decision problem is yes then it is in the corresponding language.
- The complexity class \(\mathsf{P}\) contains the recursive languages whose membership can be determined by Turing machines, bounded by a polynomial function.
- The complexity class \(\mathsf{NP}\) contains the recursive languages whose membership can be determined by a non-deterministic Turing machine, bounded by a polynomial function.
- Clearly \(\mathsf{P} \subseteq \mathsf{NP}\), however it is an undecided problem in Computer Science, as to whether \(\mathsf{P} = \mathsf{NP}\).
- A decision problem is NP-complete if it is in \(\mathsf{NP}\) and there is a polynomial time reduction to convert every instance of every other \(\mathsf{NP}\) problem to it.
- A decision problem is NP-hard if there is a polynomial time reduction of every \(\mathsf{NP}\) problem to it. The intuition is since the hardest problem in \(\mathsf{NP}\) can be reduced to it, it is at least as hard as every problem in \(\mathsf{NP}\).
- All NP-complete problems are NP-hard.
- If a problem is solvable in theory, but in practice takes too long to be solved, then it is intractable.
- \(\mathsf{EXPTIME}\) refers to decision problems, that can be decided by a deterministic Turing machine bounded by an exponential function, i.e \(2^{p(n)}\), where \(p(n)\) is a polynomial function of \(n\).
- The complexity class \(\mathsf{NEXPTIME}\) contains all problem solved decided by a non-deterministic Turing machine bounded by exponential function.
- It is known: \[ \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{EXPTIME} \subseteq \mathsf{NEXPTIME} \subseteq \mathsf{R} \subseteq \mathsf{RE} \]
- An alternative definition of \(\mathsf{NP}\) is the decision problems which can be verified in polynomial time on a deterministic Turing machine, with what is known as a “certificate”.
- This definition is equivalent to the previous, since a possible certificate for all languages in \(\mathsf{NP}\) is the series of choices, made i.e. which transitions were chosen, since a non-deterministic Turing machine offers multiple possible transition.
- Given these series of choices, which were used to find the solution, a deterministic Turing machine could check in polynomial time, that these choices were valid and thus verify the solution.