TC

  • quizzes (from last class)
  • Homework 3
  • \mathbf{P},\mathbf{NP} etc

May 5, 2026

Exercises from Homework 3

Machines vs Languages

Q: Are there problems, which provably require very large time /space to be solved?

Example 1 k\text{-}\mathtt{CLIQUE}: does a graph G contain a k-clique?

  • The input is not a word, it is a more complicated object!
  • Turing Machines read words.
  • We need to encode the input, in this case the graph, in some natural way (e.g. as a word encoding an adjacency list or an adjacency matrix).

Complexity of a problem: actually means

complexity of the corresponding language under some natural representation of inputs as words

  • Typically the complexity does not depend on the choice of the representation.
  • Sometimes it depends, and then we should be more precise (we should say which representation of inputs is considered)

(Deterministic) Time Complexity

Definition 1 A (deterministic) Turing machine M works in time t(n) (for a function t : \mathbb N \to \mathbb N) if for every input word of n symbols, M halts after at most t(n) steps.

Definition 2 A language L\subseteq \Sigma^* is decidable in time t(n) if there exists a (multitape) Turing machine M that recognizes the language and works in time t(n).

\mathbf{DTIME}(t(n)) :=\{L\subseteq\Sigma^* \mid L \text{ is decidable in time }\mathcal O(t(n))\}

\displaystyle\mathbf{P} :=\displaystyle\bigcup_{k\in \mathbb N}\mathbf{DTIME}(n^k)
i.e. all languages decidable in time p(n) for some polynomial p

\displaystyle\mathbf{EXPTIME} :=\displaystyle\bigcup_{k\in \mathbb N}\mathbf{DTIME}(2^{n^k})

Theorem 1 If f(n)=\mathcal O(g(n)), then \mathbf{DTIME}(f(n))\subseteq \mathbf{DTIME}(g(n)).

Proof. trivial (why?)

Q: If f(n)=\mathcal o(g(n)), is \mathbf{DTIME}(f(n))\subsetneq \mathbf{DTIME}(g(n))?
In other words, given asymptotically strictly more time, can we decide strictly more languages?

In general no for arbitrary functions, but yes for time-constructible functions. (next-class)

Time Hierarchy Theorem

Theorem 2 (time hierachy theorem) If f,g are time-constructible and f(n)\ln f(n) = o(g(n)), then \mathbf{DTIME}(f(n))\subsetneq \mathbf{DTIME}(g(n))\ .

Proof. maybe a proof sketch next week

Corollary 1 \mathbf{P}\subsetneq \mathbf{EXPTIME}

Nondeterministic Time

Definition 3 A nondeterministic Turing machine M works in time f(n) (for a function f : \mathbb N \to \mathbb N) if for every input word of n symbols, every run of M (not only the accepting ones!) halts after at most f(n) steps.

\mathbf{NTIME}(t(n)) := all languages decidable on a nondeterministic Turing machine working in time t(n)

Theorem 3 \mathbf{DTIME}(t(n))\subseteq \mathbf{NTIME}(t(n)) (why?)

\displaystyle\mathbf{NP} \displaystyle:=\bigcup_{k\in \mathbb N}\mathbf{NTIME}(n^k)

\displaystyle\mathbf{NEXPTIME} \displaystyle:=\bigcup_{k\in \mathbb N}\mathbf{NTIME}(2^{n^k})

Classes of complements

For every class of languages \mathscr C, the class \mathbf{co}\mathscr C is \mathbf{co}\mathscr C:=\{L\mid \overline L\in \mathscr C\}

Theorem 4 deterministic classes are equal to its co-classes, e.g. \mathbf{P}=\mathbf{coP}.
(why?)

for non-deterministic classes it is not clear at all:

  • Does \mathbf{NP}=\mathbf{coNP}?
  • Does \mathbf{NP}\cap \mathbf{coNP}=\mathbf{P}?

An alternative definition of \mathbf{NP} using witnesses

Definition 4 (polynomial time relation) A relation R\subseteq \Sigma^*\times \Sigma^* is defined as the language of words v\$w with v,w\in \Sigma^* and \$\notin \Sigma. A relation is polynomial-time if

  • R\in \mathbf{P}, and
  • there exists a polynomial p such that v\$w\in R implies |w|\leq p(|v|)

Example 2 \mathtt{HAM}: the language of (codes of) graphs in which there exists a Hamiltonian cycle.

  • R=\{ graph \$ consecutive nodes on a Hamiltonian cycle in the graph \}
  • it is easy to recognize R in polynomial time
  • the second part of R (a cycle) is not longer than the first one (a graph)

Theorem 5 L\in \mathbf{NP} \iff there exists a polynomial-time relation R s.t. L=\{v\mid \exists w, v\$w\in R\}

Proof.

(\Leftarrow) The length of witnesses is bounded by some polynomial p.

  • Create a machine M, which after the input word (nondeterministically) writes an arbitrary word of length ≤p(n) (in particular M counts the length of the word that it writes, and finishes writing it, if it gets longer than p(n))
  • M executes the (deterministic) machine recognizing R.

(\Rightarrow) L is recognized by a nondeterministic machine M in time p(n).

  • On every accepted word v there exists a sequence of transitions of M performed in consecutive steps of an accepting run; this sequence has length ≤p(|v|).
  • As R take input words together with codes of accepting runs.
    • This relation is polynomial; in particular, it can be recognized by a deterministic machine in polynomial time

Reductions

Definition 5 A language L\subseteq \Sigma_1^* is polynomial time many-one reducible (or simply polynomially) reducible to L'\subseteq \Sigma_2^* (denoted as L\leq_m^p L') if there exists a function f: \Sigma_1^*\to \Sigma_2^* computable in polynomial time s.t.

w\in L \Leftrightarrow f(w)\in L'\ .

Theorem 6  

  • if B\in \mathbf{P} and A\leq_m^p B, then A\in \mathbf{P}.
  • if A\leq_m^p B and B\leq_m^p C, then A\leq_m^p C.

Definition 6 (completeness) Given a complexity class \mathscr C, a language L is \mathscr C-complete (w.r.t. polynomial-time reductions) if

  • L\in \mathscr C, and
  • L is \mathscr C-hard, i.e. for every L'\in \mathscr C, L'\leq_m^p L.

It is surprising that complete problems exist at all!

\mathbf{NP}-completeness

Theorem 7 The language \mathtt{TMSAT}:=\{\langle M,1^t,w\rangle \mid M \text{ is a nondeterm. TM that accepts } w\text{ in at most } t\text{ steps}\} is \mathbf{NP}-complete.

Proof. (sketch)

  • \mathtt{TMSAT}\in \mathbf{NP}: simulate the run of M on w for at most t steps
  • \mathtt{TMSAT} is \mathbf{NP}-hard: Consider a language L\in \mathbf{NP}, recognized by a nondet. machine M working in polynomial time t(n). Then for every w, w\in L\iff \langle M,1^{t(|w|)},w\rangle \in \mathtt{TMSAT}, and the word \langle M,1^{t(|w|)},w\rangle can be computed in polynomial time.

\mathtt{TMSAT} is not a very useful problem.
Q: Are there natural/interesting problems that are \mathbf{NP}-complete?

\mathtt{SAT}: the language of Boolean formulas that are satisfiable, i.e. that can be set to true by some assignment of their variables.

Theorem 8 (Cook, 1971) \mathtt{SAT} is \mathbf{NP}-complete

Proof. (sketch)

\mathtt{SAT}\in \mathbf{NP}: guess the satisfying assignment \mathtt{SAT} is \mathbf{NP}-hard:

  • Fix a language L recognized by a nondeterministic machine M in time bounded by a polynomial p(n)

  • Basing on the input word w, we need to construct (in polynomial time) a formula F such that w\in L iff F is satisfiable

  • Idea: variables store a run of M on the word w, the formula ensures correctness of the run.

  • Three kinds of variables:

    • t_{ick}: in step k, the letter in the i-th cell of the tape is c
    • s_{qk}: in step k the machine is in state q
    • h_{ik}: in step k the head is on position i
      we have polynomially many variables \mathcal O((p(n))^2)

  • The formula, a conjunction of the following

    • the initial tape contents, head position, and state are as expected:
      s_{q_00}\land h_{00} \land t_{0\triangleright0}\land t_{1w_10}\land t_{2w_20}\land \cdots\land t_{nw_n0}\land t_{(n+1)\square0}\land \cdots\land t_{p(n)\square0}
    • at most one state at each moment: when 0\leq k \leq p(n) and q\neq q' (\lnot s_{qk}\lor \lnot s_{q'k})
    • at most one head position at a moment: \sim as above
    • at most one symbol in a cell at a moment: \sim as above
    • symbols not under the head remain unchanged: when 0\leq k\leq p(n) and i\neq j h_{ik}\land t_{jck} \rightarrow t_{jc(k+1)}
    • a transition is performed (an alternative over possible transitions): t_{ick}\land s_{qk}\land h_{ik} \rightarrow \bigvee (t_{ic'(k+1)}\land s_{q'(k+1)}\land h_{(i\pm 1)(k+1)})
    • acceptance: \bigvee_{k=0}^{p(n)} s_{q_{\text{accept}\,k}} This formula can be generated in polynomial time.

\mathbf{NP}-completeness

There is a long list of \mathbf{NP}-complete problems which are relevant in practice. For instance:

  • Hamiltonian path problem
  • Traveling salesman problem
  • Clique problem
  • Knapsack problem
  • Subgraph isomorphism problem
  • Subset sum problem
  • Vertex cover problem
  • Independent set problem
  • Dominating set problem
  • Graph coloring problem

\mathbf{NP}-hardness shown by reduction from some other \mathbf{NP}-complete problem (e.g., from \mathtt{SAT}).