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