Decidability

Whether a problem is solvable by an algorithm.

Decidable Problem

A problem is decidable iff a TM decider exists that halts with correct yes/no for every input.

A problem is undecidable iff no such TM exists.

Connected Graph Example

$A = \{\langle G \rangle \mid G \text{ is a connected undirected graph}\}$

$T$ marks the first node, then marks any node adjacent to a marked node. Accepts if all nodes are marked; rejects otherwise. Always halts. $A$ is decidable.

Why Undecidable Problems Exist

TMs can be encoded as strings. The set of all TMs is countable.

All languages over $\Sigma^*$ form the power set $\mathcal{P}(\Sigma^*)$, which is uncountable and strictly larger than the set of TMs.

Since there are more languages than TMs, most languages have no TM that accepts them.

Cardinality

Cardinality measures the size of a set. 2 sets have equal cardinality iff a bijection exists between them.

• Injective
  No 2 elements in $X$ map to the same element in $Y$.
• Surjective
  Every $y \in Y$ has a preimage in $X$.
• Bijective
  Both injective and surjective. Exact pairing between 2 sets.

Diagonalization

Technique for showing 2 sets have unequal cardinality by proving no bijection can exist.

Applied to $\mathbb{R}$: assume a complete listing of all reals. Construct a number differing from the $n$-th real at the $n$-th decimal digit. That number is not in the listing. Contradiction. $\mathbb{R}$ is uncountable.

Applied to languages: any enumeration of TMs leaves languages unaccounted for. Some languages have no TM.

Language Hierarchy

Nested hierarchy (innermost $\subset$ outermost):

Regular
  ⊂ Context-free
      ⊂ Decidable  (aka Recursive)
          ⊂ Turing-acceptable  (aka RE, Recursively Enumerable)
              ⊂ Universe of all languages

• Decidable
  TM decider exists. Always halts with accept/reject.
• Turing-acceptable
  TM acceptor exists. May loop forever on non-members.
• Outside RE
  No TM accepts these languages at all.

Reduction

Reduction converts instances of one problem into instances of another. $L_1 \leq L_2$ (”$L_1$ reduces to $L_2$”) means $L_2$ is at least as hard as $L_1$.

$L_1 \leq L_2$ iff a Turing-computable $f : \Sigma_1^* \to \Sigma_2^*$ exists such that:

$x \in L_1 \iff f(x) \in L_2$

$f$ converts any instance of $L_1$ into an equivalent instance of $L_2$.

Consequences:

• $L_2$ decidable $\Rightarrow$ $L_1$ decidable.
• $L_1$ undecidable $\Rightarrow$ $L_2$ undecidable.

To prove $L_2$ is undecidable: find a known undecidable $L_1$ and show $L_1 \leq L_2$.

Undecidable Problems

Self-Accepting Problem

Given TM $T$, does $T$ accept its own encoding $\langle T \rangle$?

Undecidable. Proved by diagonalization: assume a decider exists, construct a TM that contradicts it when run on its own encoding.

Accepts Problem

Given TM $T$ and string $w$, does $T$ accept $w$?

Undecidable. Direct simulation fails if $T$ loops forever on $w$.

Proved by reducing Self-Accepting to Accepts: given any TM $T$, construct $T'$ that ignores its input and runs $T$ on $\langle T \rangle$. If Accepts were decidable, Self-Accepting would be too. Contradiction.

Halting Problem

Given TM $T$ and string $w$, does $T$ halt on input $w$?

Undecidable. Proof by contradiction:

1. Assume a halting decider $Q$ exists. $Q$ takes any TM $P$ and input $I$, outputs YES if $P$ halts on $I$, NO otherwise.
2. Construct $S$. $S$ takes $W$, passes $(W, W)$ to $Q$:
   • $Q$ outputs YES $\Rightarrow$ $S$ loops forever.
   • $Q$ outputs NO $\Rightarrow$ $S$ halts with “OK”.
3. Run $S$ on itself ($W = S$):
   • $Q$ outputs YES ($S$ halts on $S$) $\Rightarrow$ $S$ loops. Contradiction.
   • $Q$ outputs NO ($S$ loops on $S$) $\Rightarrow$ $S$ halts. Contradiction.
4. $Q$ cannot exist. $\square$

Post Correspondence Problem

Formulated by Emile Post in 1946.

A domino is a tile $\left[\frac{t}{b}\right]$ with top string $t$ and bottom string $b$.

A match is a sequence of dominos (repetition allowed) where concatenating tops equals concatenating bottoms.

Determining whether a match exists is undecidable.

Hilbert’s 10th Problem

Determine whether a polynomial has an integral root.

Posed in 1900 by David Hilbert. Shown undecidable in 1970 (Matiyasevich et al.).

Single-variable case: search $x = 0, 1, -1, 2, -2, \ldots$ terminates within computable bounds. Decidable.

Multivariable case: no computable bound exists. Turing-acceptable but undecidable.

Other Undecidable Problems

For any programming language:

• Whether a program loops forever on some input.
• Whether a program ever produces output.
• Whether a program halts on a specific input.

For formal languages:

• Equivalence of 2 context-free grammars.
• Emptiness of a context-sensitive language.
• Membership of a string in a Type-0 language.

Intractable Problems

Decidable problems can still be practically unsolvable if no efficient algorithm exists.

A tractable problem has worst-case complexity $O(n^k)$ for fixed $k$.

An intractable problem has no known polynomial algorithm. Best-known algorithms are exponential.

Class P

$P$ is the class of decision problems solvable by a deterministic algorithm in polynomial time.

Finding the answer is fast.

Class NP

$NP$ is the class of decision problems whose solutions are verifiable in polynomial time by a deterministic algorithm.

Finding the answer may be slow. Checking a given answer is fast.

$P \subseteq NP$. Every problem solvable fast is also verifiable fast. Whether $P = NP$ is open.

Equivalently: solvable by a polynomially bounded nondeterministic algorithm with 3 phases:

• Guessing
  Writes an arbitrary string $s$ into memory.
• Verifying
  Deterministic check of input and $s$. Returns true or false.
• Output
  Outputs yes iff verifying returns true.

NP Problems

• Clique
  Given $G = (V,E)$ and integer $k$, does a clique of size $k$ exist?
• Graph Coloring
  Given $G = (V,E)$ and integer $k$, is $G$ $k$-colorable?
• Subset Sum
  Given set $S$ of positive integers and integer $k$, does a subset $R \subseteq S$ exist with $\sum R = k$?
• Satisfiability
  Given a Boolean formula, does a $\{0,1\}$ assignment exist that evaluates it to 1?
  • CNF: AND of clauses; each clause is OR of literals.
  • 3-CNF-SAT: satisfiability restricted to CNF with exactly 3 literals per clause.
• Hamiltonian Path
  Does a graph contain a path visiting every vertex exactly once?
• Traveling Salesperson
  Given a weighted complete graph and integer $k$, does a Hamiltonian cycle with total weight $\leq k$ exist?

NP-Completeness

NP-complete problems are the hardest problems in NP. Every other NP problem reduces to them.

$S$ is NP-hard iff every $R \in NP$ is polynomially reducible to $S$.

$S$ is NP-complete iff $S \in NP$ and $S$ is NP-hard.

If any NP-complete problem is in $P$, then $P = NP$.

Examples: SAT, clique, graph coloring, Hamiltonian path, subset sum, TSP.

Polynomial-time Reduction

$R \leq_P S$ iff a polynomial-time computable transformation $T$ exists such that:

$\text{answer for } R \text{ on } x = \text{yes} \iff \text{answer for } S \text{ on } T(x) = \text{yes}$

$S$ is at least as hard as $R$. If $R \leq_P S$ and $S \in P$, then $R \in P$.

Proving NP-Completeness

1. Show $S \in NP$: give a polynomial-time verifier.
2. Select a known NP-complete problem $R$.
3. Show $R \leq_P S$: construct a polynomial-time transformation.
4. By transitivity, all NP problems reduce to $S$.

Historical Results

Cook’s Theorem: SAT is NP-complete.

Karp’s reductions: decision versions of many optimization problems proved NP-complete via reductions from SAT.