Time Complexity

Overview

Let $M$ be a deterministic single-tape Turing machine that halts on all inputs. The running time or time complexity of $M$ is the function $f:\mathbb{N}\to \mathbb{N}$, where $f(n)$ is the maximum number of steps that $M$ uses on any input of length $n$.

Verification

A verifier for a language $A$ is an algorithm $V$ where

In the above definition, each $w\in A$ has a corresponding certificate (or proof) represented by symbol $c$. This is used to verify $w$ is indeed a member of $A$. A polynomial time verifier is a verifier that runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

Complexity Classes

TIME

Let $t$ be an asymptotically nonnegative function. The time complexity class $\text{TIME}(t(n))$ is the collection of all languages decidable by an $O(t(n))$-time deterministic single-tape Turing machine.

P

$\text{P}$ is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. In other words,

NTIME

Let $t$ be an asymptotically nonnegative function. The nondeterministic time complexity class $\text{NTIME}(t(n))$ is the collection of all languages decidable by an $O(t(n))$-time nondeterministic Turing machine.

NP

$\text{NP}$ is the class of languages that are decidable in polynomial time by a nondeterministic Turing machine. In other words,

We can equivalently characterize $\text{NP}$ as the class of languages that have polynomial time verifiers.

coNP

The complexity class containing languages that are complements of languages in $\text{NP}$ is called $\text{coNP}$. It is unknown whether $\text{coNP}$ is different from $\text{NP}$ but, generally speaking, it does seem that verifying something is not present is more difficult than verifying something is present.

NP-Hardness

A language $B$ is $\text{NP}$-hard if every $A\in \text{NP}$ is polynomial time mapping reducible to $B$.

NP-Completeness

A language $B$ is $\text{NP}$-complete if it is in $\text{NP}$ and is $\text{NP}$-hard.

Satisfiability Problem

The satisfiability problem is the problem of determining whether or not a Boolean formula is satisfiable. That is, it is the problem of determining membership in the following language:

Restricting the Boolean formulas we consider to those in CNF yield language:

Restricting the number of literals found in each clause of a cnf-formula yields the $k\text{-CNF-SAT}$ problem, otherwise known as the $k\text{-SAT}$ problem:

Cook-Levin Theorem

$\text{SAT}$ is $\text{NP}$-complete.

Model Dependence

The time complexity of a language $A$ depends on the model of computation used. Though TMs are known to be robust with respect to computability theory, variants are less robust with respect to time complexity.

Nonetheless, all "reasonable" deterministic computational models are polynomially equivalent. That is, a reasonable deterministic model can simulate another reasonable deterministic model with only a polynomial change in running time.

Likewise, all reasonable nondeterministic computation models are polynomially equivalent.

Multi-tape

A $k$-tape TM can be simulated using a single-tape TM by concatenating each of the $k$ tapes onto the one tape with some some separation symbol not found in the multi-tape TM's alphabet, e.g. #.

Define $t(n)$ such that $t(n)\ge n$. Then every $t(n)$-time multi-tape Turing machine has an equivalent $O(t^2(n))$-time deterministic single-tape Turing machine.

Nondeterministic

An NTM can be simulated using a $3$-tape TM by performing a breadth-first search over the NTM's computation tree, shown below. On each update to the address tape, the input tape is copied to the simulation tape and the computations are run again from the beginning.

Define $t(n)$ such that $t(n)\ge n$. Then every $t(n)$-time nondeterministic Turing machine has an equivalent $2^{O(t(n))}$-time deterministic single-tape Turing machine.