5. Computability and Complexity

Decision Problems

$L$ is a language over the alphabet $\Sigma$, and the string $w \in \Sigma^*$. $\omega \in L$ is a decision problem.

$L$ is decidable, reversible, computable, iff there is an algorithm that outputs if $w \in L$ or not.

The algorithm must terminate for all inputs. If there is no such algorithm, L is undecidable.

Optimization problems can be encoded into decision problems: for example, to find the length of shortest path, simply check if there a path with length less than $k$, incrementing $k$ until you get a yes.

There are uncountably many languages over the alphabet: $|\mathbb{P}(\Sigma^*)| = 2^{|\mathbb{N}|} =|\mathbb{R}|$. However, there are only a countable number of algorithms: $|\Sigma^{'*}| = |\mathbb{N}|$. Hence for most languages, there is no decision algorithm.

$L$ is semi-decidable, recursively enumerable, or partially computable, iff the algorithm outputs if $w \in L$, and doesn’t output anything if not - i.e. It does not terminate if $w \notin L$. Hence, you do not know if it is decidable or not unless it outputs the result.

Every decidable language is also semi-decidable: if no is outputted, just pass it through to an endless loop.

Some undecidable languages are semi-decidable.

If $L$ and $\overline{L}$ are both semi-decidable, then $L$ is decidable: run both algorithms simultaneously for each string; one of them is guaranteed to terminate.

Algorithms correspond to a function $f$: $\Sigma^* \rightarrow \Sigma^*$; map an input to an output, both of which are encoding using the alphabet $\Sigma$.

NB: Functions on numbers can be encoded using binary (otherwise, the alphabet would be infinite).

Semi-decidable:

• $f$: $A \rightarrow B$ is computable iff there is an algorithm that outputs $f(x) \; \forall x \in A$ and terminates for all inputs
• Partial function: $f(x) \in B$ or $f(x)$ undefined
• Partially computable if there is an algorithm that outputs $f(x)$ whenever $f(x)$ is defined

Turing Machines

• Extension of finite automata
• Infinite tape: cells that store a symbol
• Machine has read/write head over one cell on the tape
• Finite automaton portion of the Turing machine called the finite control
• Transitions may depend on the symbol under the head
• Transitions may change the symbol under the head
• The machine halts as soon as it reaches the accept or reject state

Where:

• $Q$ is the set of states
• $\Sigma$ is the input alphabet, which cannot contain the blank symbol
• $\Gamma$ is the tape alphabet; $\Sigma \subseteq \Gamma$
  • That is, the input alphabet is a subset of the tape alphabet
  • $\_ \in \Gamma \setminus \Sigma$ is the blank symbol
• $q_0$ is the start state
• $q_a \in Q$ is the accept state
• $q_r \in Q$, $q_a \neq q_r$ is the reject state
• $\delta$ is the transition function: $(Q \setminus \{ q_a, q_r \}) \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$

The TM operates as follows:

• Input is placed on the tape - all other cells are set to blank
• Starts with head over the first input symbol
• If $M$ is in state $p$ with symbol $a$ under the head, $\delta(p, a) = (q, b, X)$ is consulted
• Tape head moves in direction $X$: $L$ (left), $R$ (right), or $N$ (none)
• Transitions in the format $a/b, X$, where $a$ is the symbol that should be under the head for the transition to occur, $b$ is the symbol it is replaced with, and $X$ is the direction the head should move in
• Blank symbols can be introduced and removed

Notes:

• $M$ is deterministic
• $M$ may or may not halt
• $M$ is total if $M$ accepts all inputs $w \in Z^*$
• $M$ can be used to accept a language (ignoring tape contents), or to compute a function

Configuration

Storing the current state of the Turing machine: $(x, q, y) \in \Gamma^* \times Q \times \Gamma^*$ where:

• $q$ is the current state
• $x$ is the tape contents to the left of the head
• $y$ is the tape contents under and to the right of the head

Since only one cell on the tape can be modified at a time, a configuration relation can be used to describe transitions. e.g. where $a, b, c \in \Gamma$ and $p, q \in Q$:

• $M$ accepts $w$ if $(\epsilon , q_0, w) \rightarrow^* (x, q_a, y)$
• $M$ rejects w if $(\epsilon, q_0, w) \rightarrow^* (x, q_r, y)$
• $M$ is total if it halts on all inputs
• $L(M) = \{ w \in \Sigma^* \mid (\epsilon, q_0, w) \rightarrow^* (x, q_a, y) \text{ for some } x,y \in \Gamma^* \}$
• A language is semi-decidable if it is a language generated by a Turing machine
• A language is decidable if it is a language generated by a total Turing machine

Notes:

• $M$ computes a partial function $F(M)$: $\Sigma^* \rightarrow \Gamma^*$
• $F(M)(\omega ) = xy$ if $(\epsilon, q_0, w) \rightarrow^* (x, q, y)$ where $q \in \{ q_a, q_r \}$
• The function is partially computable if it is defined by a Turing machine
• The function is computable if it is defined by a total Turing machine

Computation Models

There are many computation models e.g. TMs with multiple tapes, pushdown automata with two stacks etc. Many of these are equivalent: they accept the same languages and compute the same functions.

Church-Turing thesis: the intuitively computable functions (that is, that humans can compute - hard to formalize) are those partially computable by a Turing machine.

Chomsky Hierarchy

Where:

• $N$ is the non-terminal set
• $\Sigma$ is the terminal set, disjoint from $N$
• $P \subseteq (N \cup \Sigma)^+ \times (N \cup \Sigma)^*$ is a finite set of productions
• $S$ is the start symbol, a non-terminal

Different grammars are obtained by restricting the form of each production $x \rightarrow y$:

• Type-0 (general): $1 \le |x|$
  • That is, the number of terminals and non-terminals on the LHS is bigger than $1$
• Type-1 (context-sensitive): $1 \le |x| \le |y|$
  • LHS can’t be smaller than the RHS
• Type-2 (context-free): $x \in N$
  • The LHS is a non-terminal
• Type-3 (regular): x$ \in N, y \in \Sigma \cup \Sigma N$
  • The LHS is non-terminal, and the RHS non-terminal, or a non-terminal followed by a terminal

Notes:

• For type-1 and type-3 grammars, the $\epsilon$ string is not covered
• As you go to more general grammars, everything gets more difficult (e.g. membership problem exponential for type-1, impossible for type-0)
• Type-1 languages are closed under the complement operator
• Type-1 languages are defined by a linearly space-bounded non-deterministic automata
  • The amount of tape that can be used is some multiple of the input size
• Every type-1 language is decidable

Undecidability

Programs can be the input of other programs e.g. compiler takes a program as input, Python interpreter.

Special Halting Problem

The following, called the special halting problem, is undecidable:

$\langle M\rangle$ is the representation of the machine in tape.

Thus, the SHP is the set of all programs which, when given itself as input, halts.

Proof

• If the SHP is decidable, $SHP = L(M_{SHP})$ for a total TM $M_{SHP}$
  • That is, $M_{SHP}$ is a total TM that checks if a given TM halts when given itself as an input
• Construct a TM $M'$ that is like $M_{SHP}$, except that it goes into an endless loop if $M_{SHP}$ accepts
• Thus, $M'$ halts when given itself as input. Why?
  • $M_{SHP}$ rejects $\langle M' \rangle$
  • $\langle M' \rangle \notin SHP$
  • $M'$ does not halt on $\langle M' \rangle$

def M_SHP(program_str):
  return True if exec(program_str)(program_str) halts else False

def M_dash(program_str):
  if M_SHP(program_str):
    while True:
      continue
  return False

M_dash(as_string(M_dash))
# If false is returned, then it does not halt so it cannot have returned false
# If it does not terminate, then it must halt, but it cannot have halted
# Hence, M_SHP cannot exist

Halting Problem

$\{ \langle M \rangle \#w \mid M \text{ halts on input } w \}$, where $\#$ is a symbol that does not appear in $\langle M\rangle$, allowing it to act as a separator.

Assume there is some total TM which determines if some program given some arbitrary string terminates. If this is possible, solving the special halting problem is trivial - just pass the specific input of $\langle M \rangle$. Since its not possible, neither is the halting problem

Some other undecidable languages:

• If problem halts on empty tape
• If two TMs are equivalent
• If TM enters a given state
• If the language generated by a given TM is a subset of some arbitrary se (as long as it is not the empty or universal set)

Complexity Classes

Running times of programs:

$t(M, x)$ returns the number of steps the (total?) TM M takes for a given input $x$ until it halts.

Function $f:N \rightarrow N$ gives upper bound on how long a function can take for a given input size: T(f) is the set of languages, with the language generated by a total TM $M$ being in $T(f)$ if $t(M, x) < f(|x|)$ for all values of $x$.

The program can be solved efficiently if it can be solved in polynomial time. These languages are in the complexity class $P$. Examples include:

• Shortest path between two nodes in a graph
• Every CFL
• $\{ x|x \text{ is a palindrome} \}$
• Deterministic primality testing

Non-Deterministic Turing Machine (NTM)

• $t(M, x)$ is the number of steps in the longest transition sequence
• $\delta: (Q \setminus \{ q_a, q_r \}) \times P( \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \})$
• Non-deterministic polynomial time is the complexity class denoted by $NP$
• $P \subseteq NP$, but does $P = NP$?
• An NTM can guess the output and then verify its correctness in polynomial time

Some problems known to be in $NP$ (and may or may not be $P$):

• Does a graph contain a path that visits every vertex exactly once?
  • Hamilton path problem
• Given sets of integers $a$ and an integer $b$, is there a subset of $a$ that sums to $b$
• Partitioning a list of integers such that the sums of the two subsets are equal
• Satisfiability formula: given logic formula with Boolean variables and operations, can it be true?

Problem Complexity

Compare problem complexities by reducing one to another:

• $A$ is polynomial-time reducible to $B$: $A \le _P B$ if there is a function that runs in polynomial time that maps every input in $A$ to every input in $B$
• Thus, if $B \in NP$, and $A \le _P B$, then $A \in NP$

NP-Complete Problems

• Must be $NP$
• Must be $NP$-hard
  • $B \le _P A \quad \forall B \in NP$

If these two conditions are met, then every other $NP$ problem is polynomial-time reducible to it. Thus, if one $NP$-complete problem is solved, then $P = NP$

Showing that a problem is $NP$-hard is difficult - there are a lot of $NP$ problems.

The satisfiability problem (SAT) was the first problem shown to be $NP$ complete:

• There is an NTM for the problem running in polynomial time
• Every problem in $NP \le _P SAT$
• $SAT \le _P 3\text{-}SAT$
  • So 3-SAT is also $NP$-complete
• $3\text{-}SAT \le _P CLIQUE$
  • So CLIQUE is also $NP$-complete
• $\dots$

Hence, there is a tree of reductions.

CLIQUE

Finding the largest subset of the graph that is complete - all pairs of nodes are connected.

SAT

Given logic formula:

Output: can the variables be set such that the formula evaluates to true?

On a NTM, guess and verify:

• Evaluating the formula once for some given set of variables: linear time
• Use NTM to transition variables between 0 and 1 and generate all possible combinations
  • Choices are possible; there is no set implementation for how the choices are picked

3-SAT

Limit the structure of logic formulas using Conjunctive Normal Form (CNF):

Every formula can be converted into CNF.

If the distributivity rule is used in highly nested formulas there is exponential blow-up as each use of it causes duplication: thus, it cannot be used.

S-SAT

Given formula in CNF with exactly 3 literals per clause: $\text{Clause = Literal OR Literal OR Literal}$

• Push down negations using de Morgan/double negation
• New variable $V_n$ for each inner node $n$ (non-literal) in the syntax tree
  • Require $V_1$, root node to be true
  • $\text{AND } V_1 \leftrightarrow V_2 \text{ AND/OR } V_3$ to be true
  • $\text{AND } V_2 \leftrightarrow \dots$ to be true
  • $\dots$
• Rewrite the equivalences as clauses:
  • $V_1 \leftrightarrow \text{ AND/OR } V_3$
  • Use definitions of $\leftrightarrow$ and $\rightarrow$ to convert them into clauses: $(V_1 \rightarrow V_2 \text{ AND/OR } V_3) \text{ AND } (V_2 \text{ AND/OR } V_3 \rightarrow V_1)$
• Expand short clauses with new variables
  • If $a = V_1 \text{ AND/OR } V_2$
  • $a = (a \text{ OR } w) \text{ AND } (a \text{ OR } !w)$
  • So now there are three variables

Result is in 3-CNF, obtained in polynomial time, is satisfiable if and only if the original formula is satisfiable.