Computational Models Cheat Sheet
Saar hagever - TAU 2022

1 Algorithm Definition

`-`	Finite set of available instructions
`-`	Made of finite instructions
`-`	Discrete steps taking finite time
`-`	Each step depends only on the previous ones
`-`	No limit to steps or space during execution

2 Turing Machine

A Turing Machine $M$ is $(Q, Σ, δ, q_{0})$

$Q (∋ q_{i}), h \notin Q$	Set of states, $h$ halting state
$Σ (∋ σ, σ^{'}, \hdots)$	Set of symbols
$q_{0} \in Q$	Initial state
$δ \subseteq (Q \times Σ) \times (Q \cup {h} \times Σ \times {L, R, -})$	is the transition function
if $(q, ▹, q^{'}, σ, D) \in δ$	then $σ = ▹, D = R$

$Σ^{*}$ is the free monoid generated from $Σ$ . $" \cdot "$ is the associative string concatenation operator. $ϵ$ is the empty string and identity element.

2.1 Configuration

A configuration $C$ of a TM $M$ is a quadruple: $(q, u, σ, v) \in (Q \cup {h}) \times Σ^{*} \times Σ \times Σ^{F})$ where $Σ^{F} = Σ^{*} \cdot (Σ ∖ {#}) \cup {ϵ}$ .

$σ$ is the currently selected symbol under the head of the machine. Short notation is $(q, u \underset{―}{σ} v)$ or $(q, w)$ when position is not needed.

2.2 Computations

A computation is a finite succession of computation steps

$(q, w) \to (q^{'}, w^{'})$	Computation step
$(q_{0}, w) \to^{*} (q^{'}, w^{'})$	Reflexive and transitive closure of comp. steps.
$(q_{0}, w) \to_{M}^{n} (q^{'}, w^{'})$	Machine $M$ computes $w^{'}$ in $n$ steps.
$↓, ↑$	Converges and diverges

2.3 T(uring)-Computability

Let $Σ, Σ_{0}, Σ_{1}$ be alphabets, let $#, ▹ \notin Σ_{0} \cup Σ_{1}$ and $Σ_{0} \cup Σ_{1} \subset Σ$ .

Let $f$ be a function $f : Σ_{0}^{*} \to Σ_{1}^{*}$ .

f

is turing computable by a machine

M

\Leftrightarrow

\forall w \in Σ_{0}^{*} : f (w) = z \Leftrightarrow (q_{0}, \underset{―}{▹} w) \to_{M}^{*} (h, ▹ z \underset{―}{#})

sectionProblems and Functions

2.4 Poly reduction

$L_{1} \leq_{P} L_{2}$ Then exsit $f \in O (n) \mapsto | f (w) | = n^{k}$ for some k

2.5 Total Function

$f : A \to B$ , subset of $A \times B$ is total $\Leftrightarrow$

$\forall a \in A \exists b \in B : (a, b) \in f$	$f$ is defined everywhere
$(a, b), (a, c) \in f \Rightarrow b = c$	uniqueness

2.6 Partial Function

$f : A \to B$ , subset of $A \times B$ is a partial function $\Leftrightarrow$

$(a, b), (a, c) \in f \Rightarrow b = c$	uniqueness
$\exists$ at least a $b \in B : f (a) = b$	not required to be defined everywhere

Theorem

Computable functions are $# (N)$ . Total computable functions are $# (N)$ . There exists functions that are not computable.

Proof ▼

Computable functions can be given a Gödel numbering. Therefore there exists a 1-1 mapping with natural numbers. All the possible total functions ${f : N \to N}$ are $2^{# (N)}$ .

Theorem

Padding Lemma: every computable function $φ_{i}$ has $# (N)$ indexes. $\forall i . \exists A_{i}$ infinite set of indexes such that $\forall y \in A_{i} . φ_{y} = φ_{i}$

Proof ▼

If a program $P_{j}$ in WHILE computes $φ_{i}$ , one can build $# (N)$ other programs that compute the same thing, semantically equal to $φ_{i}$ by just adding a skip command at the end of the program. The new program’s index will change because an effective numbering depends only on the syntactic description of the program.

Theorem

The class of Primitive Recursive functions (and extensions) does not contain all the effectively computable functions:

Proof ▼

reductio ad absurdum

1: Encode and enumerate p.r. functions	$f_{0}, \hdots, f_{n}$ . There are $N$
2: Define diagonal func. $g (x) = f_{x} (x) + 1$	Intuitively computable
3: $\forall n . g (n) \neq f_{n} (n) \Rightarrow \forall n . g \neq f_{n}$	$g$ doesn’t appear in list

Implies there is no formalism for expressing only and all total functions.

Recursion Axiom

Let $h$ be a p.r. func. in $k + 1$ variables, $g$ be a p.r. func in $k - 1$ variables. The function $f$ in $k$ variables defined as follow is then p.r.

f = {\begin{matrix} f (0, x_{2}, \hdots, x_{k}) & = & g (x_{2}, \hdots, x_{k}) & final step \\ f (x_{1} + 1, \hdots, x_{k}) & = & h (x_{1}, f (x_{1}, \hdots, x_{k}), x_{2}, \hdots, x_{k}) & iteration \end{matrix}

This represents a FOR loop. $x_{1}$ , the first variable of $f$ is the decrementing counter. $g$ is the final step. $h$ represents loop steps. This is guaranteed to terminate. One can define basic maths primitives with p.r. functions.

Theorem

Enumeration: $\exists z . \forall i, x . φ_{z} (i, x) = φ_{i} (x)$

Proof ▼

Guarantees that a formalism that expresses all computable function has an universal algorithm. Therefore there exists an Universal Turing Machine. $φ_{z} (i, x) = U (μ y . T (i, x, y)) = φ_{i} (x)$

3 Turing Machines

Deterministic TMs are seen in the Computability Theory Cheat Sheet.

3.1 K-tapes Turing Machines

Let $k \geq 1$ be the number of tapes. A k-tape TM is a quadruple $(Q, Σ, δ, q_{0})$ . Special symbols $#, ▹, \in Σ$ , while $L, R, - \notin Σ$ . Since we are only considering decision problems, $YES, NO \notin Q$ are the halting states. The transition function differs but is subject to the same restrictions as a classical TM.

δ : Q \times Σ^{k} \to Q \cup {YES, NO} \times (Σ \times {L, R, -})^{k}

3.2 IO Turing Machines

Are useful to study space complexity. Any k-tape TM $M = (Q, Σ, δ, q_{0})$ is of IO type $\Leftrightarrow δ$ is subject to the following constraints. Consider $δ (q_{1}, σ_{1}, \hdots, σ_{k}) = (q^{'}, (σ_{1}^{'}, D_{1}), \hdots, (σ_{k}^{'}, D_{k}))$

$σ_{1}^{'} = σ_{1}$	First tape is read-only
$D_{k} = R$ or $(D_{k} = -) \Rightarrow σ_{k}^{'} = σ_{k}$	Last tape is write-only
$σ_{1} = # \Rightarrow D_{1} \in {L, -}$	Input tape is right-bounded

3.3 Nondeterministic Turing Machines

A nondeterministic TM is a quadruple $N = (Q, Σ, Δ, q_{0})$ where $Q, Σ, q_{0}$ are the same as in other turing machines. They can be of IO and k-tape type. The difference rilies in the fact that

Δ \subseteq (Q \times Σ) \times ((Q \cup {YES, NO}) \times Σ \times {L, R, -})

Is not a transition function but a transition relation. The same syntax as for other TMs is used for nondet. TMs configurations and computations. A nondeterministic TM $N$ decides $I$ if and only if $x \in I \Leftrightarrow$ there exists at least a computation such that $(q_{0}, \underset{―}{▹}, x, ▹, \hdots, ▹) \to_{N}^{*} (YES, w_{1}, \hdots, w_{k})$

Note

A single computation on a nondeterministic TMs is not a tree. Many computations together, can be arranged in a tree.

The degree $d$ of nondeterminism of a NDTM $N = (Q, Σ, Δ, q_{0})$ can now be defined as $d = max {\deg (q, σ) ∣ q \in Q, σ \in Σ}$ , where $deg (q, σ) = # {(q^{'}, σ^{'}, D) ∣ ((q, σ), (q^{'}, σ^{'}, D)) \in Δ}$

4 Reductions

A (decision) problem (a set) $A$ reduces to $B$ with reduction $f$ , in symbols $A ⩽_{f} B$ when $a \in A \Leftrightarrow f (a) \in B$ . We also have that $A ⩽_{f} B \Leftrightarrow \overset{―}{A} ⩽_{f} \overset{―}{B}$ because $x \in \overset{―}{A} \Leftrightarrow x \notin A \Leftrightarrow f (x) \notin B \Leftrightarrow f (x) \in \overset{―}{B}$ .

4.1 Reduction Relations

A relation of reductions ( $⩽_{F}$ ) can be defined on a class of functions $F$ as follows, note that $⩽_{F}$ is also a partial pre-order.

A ⩽_{F} B \Leftrightarrow \exists f \in F . A ⩽_{f} B

4.2 Properties

Let $D$ and $E$ two classes of problems such that $D \subseteq E$ , and $D \subseteq$ . A reduction relation̋_F classifies $D$ and $E \Leftrightarrow \forall A, B, C$ (problems):

1: Reflexivity	$A ⩽_{F} A$
2: Transitivity	$A ⩽_{F} B, B ⩽_{F} C \Rightarrow A ⩽_{F} C$
3: $D$ closed by reduction	$A ⩽_{F} B, B \in D \Rightarrow A \in D$
4: $E$ closed by reduction	$A ⩽_{F} B, B \in E \Rightarrow A \in E$

Equivalently:

1: Identity	$id \in F$
2: Closed by composition	$f, g \in F \Rightarrow f \circ g \in F$
3:	$f \in F, B \in D \Rightarrow {x ∣ f (x) \in B} \in D$
4:	$f \in F, B \in E \Rightarrow {x ∣ f (x) \in B} \in E$

4.3 Hard and Complete Problems

If $⩽_{F}$ classifies $D$ and $E$ , then $\forall$ problems $A, B, H$ .

`-`	$A ⩽_{F} B \land B ⩽_{F} A \Rightarrow A \equiv B$
`-`	$H$ is $⩽_{F}$ -hard for $E$ if $\forall A \in E . A ⩽_{F} H$
`-`	$H$ is $⩽_{F}$ -complete for $E$ if $\forall A \in E . A ⩽_{F} H \land H \in E$

Theorem

If $⩽_{F}$ classifies $D$ and $E$ , $D \subseteq E$ and $C$ is complete for $E$ then $C \in D \Leftrightarrow D = E$

Proof ▼

$(\Leftarrow)$ is obvious. $(\Rightarrow)$ : Let $C \in D$ and $A \in E$ . By completeness, $A ⩽_{F} C$ and $A \in D$ , then $E \subseteq D$ which implies $E = D$

Theorem

Completeness is "transitive" for reductions: If $A$ is complete for $E$ , $A ⩽_{F} B$ and $B \in E$ then $B$ is complete for $E$ .

Boolean Circuit

Definition

A Boolean circuit C “computes” a (finite) function $f : {0, 1}^{n} \mapsto {0, 1}^{m}$ over De Morgan basis
A circuit ensembles is an infinite family of circuits $A = {A_{n}}_{n \in N}$ . $A_{n}$ has n input bits, $A$ has m bit output, if each $A_{n}$ has $m (n)$ output bits (i.e., m is a function from N to N, might be constant, e.g., m(n) = 1). Circuit ensemble can handle any input length, i.e., compute any (even infinite) functions, but the description size is infinite!.

Theorem

(Shanon) Every $L \in {0, 1}^{n}$ can be decided by a (De Morgan) circuit of size $O (\frac{2^{n}}{n})$

Regular language

Lemma

(pumping lemma): for every regular language $L$ , there exists $ℓ > 0$ (a.k.a. pumping length) s.t. every $s \in L$ with $| s | \geq ℓ$ can be written as $s = x y z$ with with $\forall i \geq 0 x y^{i} z \in L, | y | > 0, | x y | \neq 0$

5 Classical Results

Theorem

The class of Primitive Recursive functions (and extensions) does not contain all the effectively computable functions:

Proof ▼

reductio ad absurdum

1: Encode and enumerate p.r. functions	$f_{0}, \hdots, f_{n}$ . There are $N$
2: Define diagonal func. $g (x) = f_{x} (x) + 1$	Intuitively computable
3: $\forall n . g (n) \neq f_{n} (n) \Rightarrow \forall n . g \neq f_{n}$	$g$ doesn’t appear in list

Implies there is no formalism for expressing only and all total functions.

Resulting regular expression:

$L^{'} = {0^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = i + j}$ is regular if $L$ regular T. built NFA $Q \times {0, 1}$ , $δ^{'} ((q, 0), 0) = {(δ (q, σ), 0) : σ \in Σ^{*}} . δ^{'} ((q, 0), ϵ) = {(δ (q, 1), σ) : σ \in Σ^{*}}$
$L^{'} = {0^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = | i - j |}$ is regular if $L$ regular F. take $L = ϵ$ r = r1* r2(r4+r3r1*r2)* where: r1: initial → initial r2: initial → accepting r3: accepting → initial r4: accepting → accepting

6 Complexity Classes

\begin{array}{r} \begin{array}{c} \P = ⋃_{k \geq 1} TIME (n^{k}) & NP = ⋃_{k \geq 1} NTIME (n^{k}) \\ PSPACE = ⋃_{k \geq 1} SPACE (n^{k}) & NPSPACE = ⋃_{k \geq 1} NSPACE (n^{k}) \end{array} \\ \begin{array}{c} EXP = ⋃_{k \geq 1} TIME (2^{n^{k}}) & LOGSPACE = ⋃_{k \geq 1} SPACE (k \times \log (n)) \end{array} \end{array}

6.1 Hierarchy

LOGSPACE \subseteq \P \subseteq NP \subseteq PSPACE = NPSPACE \subset EXP \subset R \subset R E

Since $LOGSPACE ⊊ PSPACE$ , at least one of those inclusions is strict:

LOGSPACE \subseteq \P, \P \subseteq NP, NP \subseteq PSPACE

It is not yet know which one of those is a strict inclusion.

Theorem. $LOGSPACE \subseteq \P$ . Proof. Let $I \in LOGSPACE$ . There $\exists$ a TM that computes $x \in I$ in $\O (\log \abs x)$ space. $M$ can range through $\O (\abs x \log \abs x # Q # Σ^{\log \abs x})$ configurations. A halting computation cannot cycle on configurations. So M computes in $\O (\abs x^{k})$ for some $k$ .

Theorem. (Savitch) $NPSPACE = PSPACE$ .

Theorem. Hierarchy of time and space. If $f$ is appropriate, then $TIME (f (n)) ⊊ TIME ((f (2 n + 1))^{3})$ , and $SPACE (f (n)) ⊊ SPACE (f (n) \times \log f (n))$ . Corollary. $\P ⊊ EXP$
Proof. $\P \subset EXP$ is obvious because $2^{n}$ grows faster than any polynomial. It is strict because $\P \subseteq TIME (2^{n}) ⊊ TIME ((2^{(2 n + 1)})^{3}) \subseteq TIME (2^{n^{2}})$ . This corollary, together with the fact that $NTIME (f (n)) \subseteq TIME (c^{f (n)})$ lets us conclude that $NP \subseteq EXP$ .

Theorem. Hierarchy 2. Let $f$ be an appropriate measuring function, and $k$ a constant. Then

$SPACE (f (n)) \subseteq NSPACE (f (n))$	$TIME (f (n)) \subseteq NTIME (f (n))$
$NSPACE (f (n)) \subseteq TIME (k^{\log n + f (n)})$

Resulting regular expression:

L_{2} = {y : \exists x, z s . t . | x | = | z | a n d x y z \in L}

(Example) is regular.onsider some DFA for $L$ . For every $n \geq 0$ , let $A_{n}$ be the set of states $s$ such that there is *some* word of length $n$ which leads the DFA from the initial state to $s$ . Let $B_{n}$ be the set of states $t$ such that there is *some* word of length $n$ which leads the DFA from $t$ to an accepting state. Finally, for any two states $s, t$ , let $R_{s, t}$ be the (regular) set of words leading the DFA from $s$ to $t$ . We have

L_{2} = ⋃_{n \geq 0} ⋃_{\begin{matrix} s \in A_{n} \\ t \in B_{n} \end{matrix}} R_{s, t} .

Since there are only finitely many possibilities for $s, t$ , the union is in fact finite, and so regular

7 Theorems on Complexity of Turing Machines

Theorem

Reduction of tapes Let $M$ be a $k$ -tape TM, deciding $I$ in deterministic time $f$ , then $\exists$ a 1 tape TM $M^{'}$ that decides $I$ in time $\O (f^{2})$

Proof ▼

(Only a draft): Build a 1 tape TM $M^{'}$ by introducing two symbols $▹^{'}$ and $◃^{'}$ to denote the start and end of the $k$ -th tape. Introduce $# Σ$ new symbols $\overset{―}{σ_{i}}$ to remember each tape’s head location. To generate the initial configuration $(q, ▹ ▹^{'} x ◃^{'} (▹^{'} ◃^{'})^{k})$ , $2 k + # Σ$ states and $\O (\abs k)$ steps are needed. To simulate a move of $M$ , $M^{'}$ iterates the input datum from left to right, and back, 2 times: find the marked $\overset{―}{σ_{i}}$ symbols, the second time write the new symbols. If a tape has to be extended, the $◃^{'}$ parens have to be moved and a cascade happens. This takes $\O (f (\abs x))$ time, for each move of $M$ . Since $M$ takes $\O (f (\abs x))$ time to compute an answer, $M^{'}$ will take $\O (f (\abs x)^{2})$

Corollary

Parallel machines are polinomially faster than sequential machines.

Theorem. Linear speedup If $I \in TIME (f)$ , then $\forall ϵ \in R^{+} . I \in TIME (ϵ \times f (n) + n + 2)$ . Proof. (Draft): Build $M^{'}$ from $M$ solving $I$ , compacting $m$ symbols of $M$ into 1 of $M^{'}$ , in function of $ϵ$ . The states of $M^{'}$ will be triples $[q, σ_{i_{1}}, \hdots, σ_{i_{m}}, k]$ meaning the TM is in state $q$ and has cursor on $k$ -th symbol of $σ_{i_{1}}, \hdots, σ_{i_{m}}$ . $M^{'}$ then needs 6 steps to simulate $m$ steps of $M$ . Therefore, $M^{'}$ will take $\abs x + 2 + 6 \times ⌈ \frac{f (\abs x)}{m} ⌉$ . Then $m = ⌈ \frac{6}{ϵ} ⌉$ . □

Same principle can apply to $SPACE$ with linear space compression. If $I \in SPACE (f (n))$ , then $\forall ϵ \in R^{+} . I \in SPACE (ϵ \times f (n) + 2)$

Theorem

For each k-tape TM $M$ that decides I in deterministic time $f$ there exists an IO TM $M^{'}$ with k+2 tapes that computes I in time $c \times f$ for some constant $c$ .

Proof ▼

$M^{'}$ copies the first $M$ tape to the second tape, in $\abs x + 1$ steps. Then, $M^{'}$ operates identically to $M$ . If and when $M$ halts, $M^{'}$ copies the result to the tape $k + 2$ , in at most $f (\abs x)$ steps. $M^{'}$ computation was $2 f (\abs x) + \abs x + 1$ steps long.

Theorem

Exponential loss in determinization, or bruteforce If $I \in N T I M E (f (n))$ and is computed by $k$ -tape $N$ , it can also be computed by a deterministic TM $M$ with $k + 1$ tapes in time $\O (c^{f (n)})$ with an exponential loss of performance. In short, $NTIME (f (n)) \subseteq TIME (c^{f (n)})$

Proof ▼

Let $d$ be the degree of nondeterminism of $N$ . $\forall q \in Q, σ \in Σ$ sort $Δ (q, σ)$ lexicographically. Every computation of length $t$ carried by $N$ is a sequence of choices that can be seen as a sequence of natural numbers $(c_{1}, \hdots, c_{t})$ with $c_{i} \in [0. . d - 1]$ . The det. TM $M$ considers these successions in an increasing order, visiting the tree of nondeterministic computations, one at a time. Therefore $M (x) ↓ \Leftrightarrow N (x) ↓$ , also, all the possible simulations can be $\O (d^{f (n) + 1})$ .

Space complexity

\begin{array}{r} \begin{array}{c} L = D S P A C E (\log (n)) & N L = N S P A C E (\log (n)) \\ PSPACE = ⋃_{k \geq 1} SPACE (n^{k}) & c o - N L = N L D T I M E (t (n)) \subseteq D S P A C E (t (n)) \end{array} \end{array}

STCON,PATH is NL-complete under log reductions.

NL clousre If the language $A$ is $N L$ -complete then

1. $A \in N L$ 2. Each problem in $N L$ is logspace reducible to $A$

Since $c o N L = N L$ each problem in $c o N L$ is logspace reducible to $A$ as well. Thus $A$ is $c o N L$ -complete.

Any $L \in NP$ have Log Verifier for $L$ is D-TM with 3 types $(w, c$ ,working type) $V$ run in Poly time $| x |$ and using $\log (| x |)$ types from working type. if $x \in L$ exsit $w$ s.t $V$ accept . if $x \notin L$ for all $w$ $V$ reject. $L \in N L \Leftrightarrow$ exsit Right only log time verifier.

Composition of space-bounded functions

is a bit tricky: Thm: if $f$ and $g$ are computable in space $s_{f} (n) . g_{f} (n) .$ respectively, then $g f$ is computable in space (with $m_{f}$ being a bound on the output length of $f$ ).

s_{f} (n) + \log (m_{f} (n)) + \log (m_{f} (n))

Randomized

Theorem

The class RP consists of all languages L that have a polynomial-time randomized algorithm A with the following behavior:
if $x \in L,$ then A accept $x$ in prob at most $\frac{1}{2}$ . and if $x \notin L$ A always reject

\cup_{c \geq 0} R P (2^{- n^{c}}) = N P RP (n^{- c}) = RP (\frac{1}{2}) = RP (1 - 2^{- n^{c}})

Theorem

The class BPP consists of all languages L that have a polynomial-time randomized algorithm A with the following behavior:
if $x \in L,$ then A accept $x$ in prob $\geq \frac{3}{4}$ . and if $x \notin L$ A accept in prob $\leq \frac{1}{4}$

c o - RP = B P P (\frac{1}{2}, 1) B P P (α - n^{- c}, α + n^{- c}) = B P P (2^{- n^{c}}, 1 - 2^{- n^{c}})

Theorem

(random algo) Given n digits strings $a, b \in R^{n}$ and $x \in {0, 1}^{n}$ then $Pr (a x = b x) \leq 1 / 2$

Proof ▼

supose $a_{j} \neq b_{j}$ Let $α = \sum a_{i} x_{i}, β = \sum b_{i} x_{i}$ when $i \neq j$ . then $a x = α + a_{i} x_{i}$ , $b x = β + b_{i} x_{i}$ then

a x - b x = (α - β) + (a_{i} - b_{i}) x_{i} Pr (a x - b x = 0) = Pr (x_{i} \frac{α - β}{b_{i} - a_{i}}) \leq 1 / 2

Theorem

(Adelman’s Theorem) Every $L \in B P P$ can be decided by a family ${C_{n}}_{n \in N}$ of poly-size circuts

$PP=RP$ consequences

PP = RP, coPP = coRP, PP = coPP = coRP = RP = ZPP = BPP \subseteq P / poly

If $PP = RP$ then you have a collapse to the first level, namely $PH = NP$ . Assume $PP = RP$ , since $PP$ is closed under complement we have $RP = c o RP = ZPP$ , thus $PP = ZPP$ .

Let $L$ be a language in ${PP}^{ZPP}$ , then there exists a probabilistic polynomial time Turing machine with access to a $ZPP$ oracle $O$ , call it $M_{O}$ , such that:

$x \in L \Rightarrow Pr [M_{O} accepts x] > \frac{1}{2}$ , and

$x \notin L \Rightarrow Pr [M_{O} accepts x] \leq \frac{1}{2} - \frac{1}{2^{n^{c}}}$ .

Where $n^{c}$ is the running time of $M_{O}$ (in the standard definition, the second inequality appears with $\leq \frac{1}{2}$ , however it can be improved to $< \frac{1}{2}$ and thus to the above).

Suppose that the Turing machine which decides $O$ has expected runtime $n^{d}$ . Now, let us look at the machine $M$ , which replaces each oracle call of $M_{O}$ by a $t$ steps simulation of the $ZPP$ machine for $O$ , and repeats this simulation $k$ times. If we come upon an oracle call, for which this process did not result in an answer (none of the $k$ $t$ -steps simulations halted), then $M$ rejects.

Let $H$ denote the event that all of the simulations halted in the given time, then:

$Pr [M accepts x] = Pr [M accepts x | H] Pr [H] + Pr [M accepts x | \overset{―}{H}] Pr [\overset{―}{H}] = Pr [M accepts x | H] Pr [H] = Pr [M_{O} accepts x] Pr [H]$ .

Thus, we have:

$x \in L \Rightarrow Pr [M accepts x] > \frac{1}{2} Pr [H]$ , and

$x \notin L \Rightarrow Pr [M accepts x] \leq (\frac{1}{2} - \frac{1}{2^{n^{c}}}) Pr [H] \leq \frac{1}{2} - \frac{1}{2^{n^{c}}}$ .

By Markov’s inequality, a single simulation does not halt with probability $\leq \frac{n^{d}}{t}$ , so $k$ $t$ -steps simulations do not output an answer with probability $\leq {(\frac{n^{d}}{t})}^{k}$ . By the union bound we have $Pr [H] \geq 1 - n^{c} {(\frac{n^{d}}{t})}^{k} \geq 1 - \frac{1}{2^{n^{c}}}$ , for $t = 2 n^{d}$ and $k = 2 n^{c}$ . In this case $M$ acheives the following separation:

$x \in L \Rightarrow Pr [M accepts x] > \frac{1}{2} (1 - 2^{- n^{c}})$ , and

$x \notin L \Rightarrow Pr [M accepts x] \leq \frac{1}{2} - 2^{- n^{c}} < \frac{1}{2} - \frac{1}{2} 2^{- n^{c}}$

Which proves $L \in PP$ , since we can replace the constant $\frac{1}{2}$ with any function $f (x) \in FP$ .

change probability in definition of PP

Lets say a separation using $p \in Q$ exists for $L \subseteq Σ^{*}$ if there exists a polynomial probabilistic Turing machine $M$ such that:

$x \in L \Rightarrow Pr [M accepts x] > p$ $x \notin L \Rightarrow Pr [M accepts x] < p$

$L \in P P$ iff there exists a separation for $L$ using $\frac{1}{2}$ (we can use a strong inequality in both cases). We proceed to show that $\forall p, q \in (0, 1) \cap Q$ , if there exists a separation for $L$ using $p$ , then there exists a separation using $q$ . Now, given a machine $M_{p}$ with separation $p$ for $L$ , lets consider a machine $M_{q}$ , which starts by tossing an $α$ -biased coin. If the outcome is $1$ then it accepts, otherwise it simulates $M_{p}$ on the input and returns it’s answer.

Since we want $M_{q}$ to be polynomial in the worst case, we restrict the simulation of the $α$ -biased coin to a certain number of iterations, such that the simulation halts with probability $1 - ϵ$ (this can be done for any $ϵ > 0$ , simply use the fact that the simulation runs in expected constant time, and apply Markov’s inequality). If the simulation didn’t halt, $M_{q}$ accepts. In this case we have:

$Extra \left or missing \right$ M_q $a c c e p t s x$ =ε+(1-ε)α+(1-α)M_p $a c c e p t s x$ , so:

$Extra \left or missing \right$ M_q $a c c e p t s x$ > ε+(1-ε)α+(1-α)p

$Extra \left or missing \right$ M_q $a c c e p t s x$ < ε+(1-ε)α+(1-α)p This means it is enough to require $q = ϵ + (1 - ϵ) (α + (1 - α) p)$ . Equivalently, $α = \frac{q - p - ϵ (1 - p)}{1 - ϵ}$ .

Since $p, q \in (0, 1) \cap Q$ , if $q > p$ we can find a small rational $ϵ$ and rational $α \in (0, 1)$ to satisfy this. If $p > q$ you can change $M_{q}$ to reject when the outcome of the $α$ -biased coin is 1. When this equality holds, $M_{q}$ achieves $q$ separation for $L$ and we are done.

CircuitSat $\in$ DTIME $(2^{n})$ consequences

$CircuitSat \in DTIME (2^{n})$ does not imply $NP \subseteq DTIME (2^{n})$ since the reduction might increase the input’s size. Suppose for example that $L \in N P$ and the reduction from $L$ to $CircuitSat$ maps strings of length $n$ to strings of length $n^{c}$ (for all $n \in N$ ), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^{c}}$ time algorithm for $L$ .

If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$ , then $N P \neq E X P$ , since $n^{O (\log n)}$ is closed under polynomial transformations, i.e. $n \mapsto n^{c}$ .

P/poly $= \cup_{c \in N}$ SIZE $(n^{c})$ consequences

If NEXPTIME $\subset P / p o l y$ then NEXPTIME = EXPTIME. Proof that $B P P \subseteq P / P o l y$ Let L be a language in BPP, and let $M (x, r)$ be a polynomial-time algorithm that decides $L$ with error $\leq 1 / 3$ (where x is the input string and r is a set of random bits).

Construct a new machine $M^{'} (x, r)$ , which runs $M, 48 n$ times and takes a majority vote of the results (where $n$ is the input length and R is a sequence of $48 n$ independently random $r^{'} s$ ). Thus, $M^{'}$ is also polynomial-time, and has an error probability $\leq 1 / e$ by the (chernof). If we can fix $R$ then we obtain an algorithm that is deterministic.

If $Bad (x)$ is defined as ${R : M (x, R) is incorrect}$ , we have:

: $\forall x {Prob}_{R} [R \in Bad (x)] \leq \frac{1}{e^{n}} .$ >

The input size is ”n”, so there are 2<sup>”n”</sup> possible inputs. Thus, by the [[union bound]], the probability that a random ”R” is bad for at least one input ”x” is

: ${P r o b}_{R} [\exists x R \in Bad (x)] \leq \frac{2^{n}}{e^{n}} < 1.$

In words, the probability that ”R” is bad for some ”x” is less than 1, therefore there must be an ”R” that is good for all ”x”. Take such an ”R” to be the advice string in our ”’P/poly”’ algorithm.

Prove that PP is closed under complement

algorithm A with the property that $x \in L \Rightarrow \Pr [A (x) = 1] > \frac{1}{2}$ and $x \notin L \Rightarrow \Pr [A (x) = 1] \leq \frac{1}{2}$ .

> Let $f (| x |)$ be the > polynomial upper bound on the running time of A on input x. Thus A > makes at most $f (| x |)$ random coin flips during its execution. In > particular, $Missing superscript or subscript argument$ .

I understand that:

- By definition of PP, $x \in L \Rightarrow \Pr [A (x) = 1] > \frac{1}{2}$ . It means that if indeed $x \in L$ , more than half of the possible coin flip combinations would cause the algorithm to accept. - The algorithm’s running time is bound by $f (| x |)$ , then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $Missing superscript or subscript argument$ .

But why is it so obvious that $Missing superscript or subscript argument$

x \notin L \Rightarrow Pr [A^{'} acc x] \leq \frac{1}{2} \cdot (1 - \frac{1}{2^{f (| x |) + 1}}) < \frac{1}{2}

and x \in L \Rightarrow Pr [A^{'} acc x] \geq (\frac{1}{2} + \frac{1}{2^{f (| x |)}}) \cdot (1 - \frac{1}{2^{f (| x |) + 1}}) > \frac{1}{2} .

This justifies the assumption (since A is still a polynomial-time probabilistic algorithm) and completes the proof.

Theorem

(extended rice) Let $C \subset R E$ s.t $Σ^{*} \notin C, C \neq \emptyset .$ then $L_{C} \notin R E$

L_{C} = {⟨ M ⟩ : M is TM and L (M) \in C} \notin R E

Proof ▼

$\overset{―}{A C C} \leq_{m} L_{C}$ and Let $M_{A}$ be TM that accept some $A \in C$ . Define $f (⟨ M, w ⟩) \mapsto ⟨ B_{M, w} ⟩$ ,
$B_{M, w}$ On input $x$ : Emulate $M_{A} (x)$ and $M (w)$ in parallel, and accept if one of them does.

⟨ B_{M, w} ⟩ \in \overset{―}{A C C} \Rightarrow L (B_{M, w}) = A \in C ⟨ B_{M, w} ⟩ \notin \overset{―}{A C C} \Rightarrow L (B_{M, w}) = Σ^{*} \notin C

Rice extended(not the version we saw)

theorem Given a property $S \subseteq R E$ , the language

L_{S} = {⟨ M ⟩ ∣ L (M) \in S}

is recursively-enumerable ( $L_{S} \in R E$ ) if and only if all the following three statements jointly hold
1. For any two $L_{1}, L_{2} \in R E$ , if $L_{1} \in S$ and also $L_{1} \subseteq L_{2}$ then also $L_{2} \in S$ .
2. If $L_{1} \in S$ then there exists a finite subset $L_{2} \subseteq L_{1}$ so that $L_{2} \in S$ .
3. The set of all *finite* languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L \in S$ ).

Proof ▼

If (1,2) hold, but (3) does not, then $L_{S} \notin R E$ *. Let’s assume that $L_{S} \in R E$ , and we’ll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M_{L}$ that accepts only the words in $L$ , and now we run the machine of $L_{S}$ on $M_{L}$ (remember - we assumed $L_{S} \in R E$ , so there is a machine that accepts $L_{S}$ !). If $L \in S$ then $⟨ M_{L} ⟩ \in L_{S}$ and since $L_{S} \in R E$ , its machine will say yes on the input $⟨ M_{L} ⟩$ , and we are done.
If (2,3) hold, but (1) does not, then $L_{S} \notin R E$ *. We assume that $L_{S} \in R E$ and we’ll show that we have a way to decide $H P$ , leading to a contradiction.

Because condition (1) doesn’t hold, there is a language $L_{1} \in S$ and a superset of it, $L_{2} \supseteq L_{1}$ so that $L_{2} \notin S$ . Now we are going to repeat the argument used in Section 4 to decide $H P$ : given an input $(⟨ M ⟩, x)$ for $H P$ , we construct a machine $M^{'}$ whose language is $L_{1}$ if $(⟨ M ⟩, x) \notin H P$ or otherwise, its language is $L_{2}$ . Then, we can decide $H P$ : either $M$ halts on $x$ , or the RE-machine for $L_{S}$ accepts $M^{'}$ ; we can run both in parallel and are guaranteed that at least one will halt.

Let’s give the details of constructing $M^{'}$ (on input $x^{'}$ ):

1. Do the following in parallel: 1.1 run $M$ on $x$ . 1.2 run the machine of $L_{1}$ on $x^{'}$ 2. If 1.2 halts and accepts - accept. 3. If 1.1 halts: run the machine of $L_{2}$ on $x^{'}$ .

Why does this work? If $(⟨ M ⟩, x) \notin H P$ then 1.1 never halts, and $M^{'}$ accepts exactly all the inputs that are being accepted at step 1.2, so $L (M^{'}) = L_{1}$ . On the other hand, if $(⟨ M ⟩, x) \in H P$ then, at some point step 1.1 halts and $M^{'}$ accepts exactly $L_{2}$ . It may happen that $1.2$ accepts beforehand, but since $L_{1} \subseteq L_{2}$ , this doesn’t change the language of $M^{'}$ in this case.
If (1,3) hold, but (2) does not, then $L_{S} \notin R E$ *. Again, we will assume $L_{S} \in R E$ and show that $H P$ becomes decidable, which is a contradiction.

If condition (2) doesn’t hold, then for any $L_{1} \in S$ , all its finite subsets $L_{2} \subseteq L_{1}$ satisfy $L_{2} \notin S$ (note that $L_{1}$ must be infinite, since $L_{1} \subseteq L_{1}$ ). As in the above, in order to decide $H P$ for a given input $(⟨ M ⟩, x)$ , we construct a machine $M^{'}$ whose language is $L_{1}$ if $(⟨ M ⟩, x) \notin H P$ and some finite $L_{2}$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M^{'}$ we constructed. The machine $M^{'}$ (on input $x^{'}$ ) does:

1. Runs $M$ on $x$ for $| x^{'} |$ steps. 2. If $M$ halts during step 1 – reject 3. Otherwise, run the machine of $L_{1}$ on $x^{'}$ .

It holds that, if $(⟨ M ⟩, x) \in H P$ , then at some point, say after 1000 steps, $M$ halts on $x$ . Therefore, step 1 will halt on (and reject) any input $x^{'}$ of length $> 1000$ . Therefore, in this case, $L (M^{'})$ is **finite**. Also note that $L (M^{'}) \subseteq L_{1}$ , and in particular, by our assumptions on the invalidity of condition (2), we have that $L (M) \notin S$ .

On the other hand, if $(⟨ M ⟩, x) \notin H P$ , then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L (M) = L_{1}$ and in particular, $L (M) \in S$ .

We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L_{S}$ , that is, $L_{S} \in R E$ . In other words, we need to show a machine $M_{S}$ so that for any input $⟨ M ⟩$ for which $L (M) \in S$ , the machine accepts this input, $M_{S} (⟨ M ⟩) \to accept$ .

Here is how the machine $M_{S}$ behaves (on input $⟨ M ⟩$ ):

1. Let $M_{enum S}$ be the machine that enumerates all the finite languages in $S$ , guaranteed by condition (3). 2. Run the following in parallel for $i = 1, 2, . . .$ 2.1 Run $M_{enum S}$ until it outputs the language $L_{i}$ 2.2. Check if $M$ accepts all the words of $L_{i}$ (run $M$ on these words, again in parallel). 2.3. If for some $i$ , $M$ accepts all the words of $L_{i}$ – accept.

Why does it work? If $L (M) \in S$ then it has a finite subset $L_{j} \in S$ , and once $M_{enum S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L (M) \notin S$ it cannot be accepting all the words in $L_{i}$ for any $i = 1, 2, . . .$ . Indeed, by condition (1), any $L^{'} \supseteq L_{i}$ is also in $S$ , so if $M$ accepts all the words in $L_{i}$ for some $i$ , then $L (M) \supseteq L_{i}$ and thus $L (M) \in S$ , in contradiction.

Given a non trivial property

S ⊊ R E

, so that

\emptyset \in S

, the language >

L_{S} = {⟨ M ⟩ ∣ L (M) \in S}

> is not recursively-enumerable, that is,

L_{S} \notin R E

Prove/ Disprove

claim

For language L s.t L satisfies pumping lemma with pumping constant $ℓ$ ,
$L | | L$ satisfies pumping lemma with pumping constant $2 ℓ$

Proposition 1

$RE$ is not closed under complement

Proposition 2

$c o RE$ is closed under intersection.

Proposition 3

$R$ is closed under Kleene star.

Proposition 4

$RE$ is closed under Prefix, but $R$ is not closed under Prefix,

Prove: If $L_{1} \leq_{m} L_{2}$ and $L_{2} \leq_{m} L_{3},$ then $L_{1} \leq_{m} L_{3} .$
Disprove: If $L_{1} \leq_{m} L_{2}$ and $L_{2} \leq_{m} L_{1},$ then $L_{1} = L_{2} .$
Disprove: If $L_{1} \subseteq L_{2}$ then $L_{1} \leq_{m} L_{2} .$
Disprove: For every $L_{1}, L_{2}$ , then $L_{1} \leq_{m} L_{2}$ or
Prove: If $L$ is regular, then $L \leq_{m} H A L T$
For every nontrivial $L_{1}, L_{2} \in P, L_{1} \leq L_{2}$ TRUE
For every nontrivial $L_{1}, L_{2} \in N P, L_{1} \leq_{P} L_{2}$ Equivalent to an Open Problem
There exists a language in $RE$ that is complete w.r.t polynomial-time reductions. TRUE.
If there exists a deterministic TM that decides SAT in time $n^{O (\log n)}$
Then every $L \in N P$ is decidable by a deterministic TM in time $n^{O (\log n)}$ . TRUE.

8 Determine if $L$ in $P$

Input: Sets $A_{1}, . . ., A_{n}$ , and a number $k$ .
Question: do there exist $k$ mutually disjoint sets $A_{i 1}, . . ., A_{i k}$ not in $P$
Input: Sets $A_{1}, . . ., A_{n}$ .
Question: do there exist 3 mutually disjoint sets $A_{i}, A_{j}, A_{k}$ in $P$
Input: Sets $A_{1}, . . ., A_{n}$ , and a number $k$ .
Question: do there exist $k$ sets such that $A_{i 1}, . . ., A_{i k}$ such that $A_{i} \cap A_{j} \neq \emptyset$ not in $P$
Input: a CNF formula $ψ$ with at most 50 variables.
Question: does there exist an assignment that satisfies $ψ$ in $P$
Input: a CNF formula $ψ$ with at most 50 clauses.
Question: does there exist an assignment that satisfies $ψ$ in $P$
Input: a 3CNF formula $ψ$ with even number of variables.
Question: does there exist an assignment that satisfies $ψ$ and gives $T r u e$ for exactly one half of the variables? not in $P$
Input: undirected graph $G$ , a number $k$ .
Question: does there exist in $G$ a clique of size at least $k$ or an independent set of size at least $k$ ? not in $P$

Resulting regular expression:

L_{2} = {y : \exists x, z s . t . | x | = | z | a n d x y z \in L}

L_{2} = ⋃_{n \geq 0} ⋃_{\begin{matrix} s \in A_{n} \\ t \in B_{n} \end{matrix}} R_{s, t} .

Since there are only finitely many possibilities for $s, t$ , the union is in fact finite, and so regular.

8.1 Examples

$L = {⟨ M ⟩ : M$ is a TM and $| L (M) | > 10} \in RE / R$
$L = {M : ⟨ M ⟩ is a TM that accepts 1 but does not accept 0} \in \overset{―}{RE \cup co- RE}$
$L = {⟨ M_{1}, M_{2} ⟩ : M_{1}, M_{2}$ are TMs and $L (M_{1}) \cap L (M_{2}) = \emptyset} \in co- RE / R$
$L = {⟨ M_{1}, M_{2} ⟩ : M_{1}, M_{2}$ are TMs and $L (M_{1}) \subseteq L (M_{2})} \in \overset{―}{RE \cup co- RE}$
$L_{n} = {w 0 w_{n} | w \in {0, 1}^{*} \land w_{n} \in {0, 1}^{n - 1}}$ is Regular
$L_{1} = {w : # a (w) \geq # b (w)} over Σ = {a, b, c}$ $L_{1}$ is not regular
$L_{2} = {w : | w | \in N_{e v e n} \land w = w^{R})} over$ $L_{2}$ is not regular
$L_{4} = {w : | w | \in N s.t | w | = n^{3}} over$ $L_{4}$ is not regular
$L = {⟨ M ⟩ | M$ is a TM and there exists an input on which M halts in less than $| M |$ steps $} \in R$
$L = {⟨ M ⟩ | M$ is a TM and $| L (M) | \leq 3} \in$ co-RE reduce $\overset{―}{H A L T}$ . idea copies M and x to its tape, and runs M on x; it accepts if M halts on x.
$L = {⟨ M ⟩ | M$ M is a TM and $| L (M) | \geq 3} \in$ RE reduce $H A L T$ . It erases w, puts M and x on its tape, and runs M on x and accepts if M halts on x.
$L = {⟨ M ⟩ | M$ is a TM that accepts all even numbers $} \in$ not RE
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is finite $} \in$ not RE
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is infinite $} \in$ not RE
$L = {⟨ M ⟩ |$ is a TM and $L (M)$ is countable $} \in$ R This is the language of all TM’s, since there are no uncountable languages ( finite alphabets and finite-length strings).
$L = {⟨ M ⟩ | M$ is a TM and $L (M)$ is uncountable $} \in$ R This is the empty set
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) \cup L (M_{2})} \in$ RE. reduce HALT s.t $⟨ M, x ⟩ \mapsto ⟨ M^{'}, M^{'} ⟩$ $⟨ M, x ⟩$ halts on $x \Rightarrow M^{'}$ accepts all strings, and in particular it accepts $ϵ \Rightarrow ϵ \in L (M^{'}) \cap L (M^{'})$ .
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) \cap L (M_{2})} \in$ RE.
$L = {⟨ M_{1}, M_{2} ⟩ |$ are TM’s and $ϵ \in L (M_{1}) / L (M_{2})} \in$ not RE.
$\overset{―}{H A L T} (M, x) \mapsto (M_{1}, M_{2}) .$ s.t $L (M_{1}) = Σ^{*}$
$L = {⟨ M ⟩ | M$ is a TM. and $M_{0}$ halt on all input, and $M_{0} \in L (M)} \in$ RE using Rice $C = {L \in R E : M_{0} \in L}$
$L = {⟨ M ⟩ | M$ is a TM. and $M_{0}$ halt on all input, and $M \in L (M_{0})} \in$ R
$L = {⟨ M ⟩ | M$ is a TM. and $x$ is str and there exists a TM, $M^{'}$ , such that $M \notin L (M^{'}) \cap L (M)} \in$ R
$L = {⟨ M ⟩ | M$ is a TM. , and there exists an input whose length is less than 100, on which M halts $} \in .$ RE
$L = {⟨ k, x, M_{1}, \dots M_{k} ⟩ | \forall i M$ is a TM, and at least $k / 2$ TM’s of halt on x $} \in .$ RE its $\emptyset$ reduce $H A L T (M, X) \mapsto (2, x, M, M^{'})$
$L = {⟨ M ⟩ | M$ is a TM and M halts on all palindromes . $} \in .$ not RE . $\overset{―}{H A L T} (M, w) \mapsto M^{'}$ on input x works as follows: $M^{'}$ runs M on w for $| x |$ steps: if M halts on w within $| x |$ steps, reject, otherwise accept.(if $x$ is polindrome)
$L = {⟨ M ⟩ | M$ is a TM and $L (M) \cap {a^{2^{n}}}}$ is empty. $} \in .$ not RE $\overset{―}{H A L T} (M, w) \mapsto M^{'}$ $M^{'}$ on input x: erase x, and run M on w. If M halts on w then $M^{'}$ accepts.
$L = {⟨ M ⟩ | M$ is a TM that halts on all inputs and $L (M) = L^{'}$ for some undecidable language $L^{'}$ . $} \in .$ R
$L = {⟨ M ⟩ | M$ is a TM and M accepts (at least) two strings of different lengths . $} \in .$ RE
$L = {⟨ M ⟩ | M$ M is a TM such that both $L (M)$ and $\overset{―}{L (M)}$ are infinite . $} \in .$ not RE M’ on input x works as follows: if x is of odd length, accept. if x is of even length, run M on w. If M halts, accept.
$(M, w) \in \overset{―}{H A L T} \Rightarrow M$ does not halt on $w \Rightarrow M^{'}$ accept all odd length str and reject all even. $\Rightarrow L (M)$ contain even-length strings, $| L | = inf$
$L = {⟨ M ⟩ | M$ is a TM, and $| L (M) |$ is prime. $} \in .$ not RE $M^{'}$ on input x: if x is one of the first three strings (in lexicographic order) of $Σ *$ , then accept. Otherwise, run M on w. If M halts on w, and x is the 4 th string in $Σ *$ accept; otherwise, reject.
$L = {⟨ M ⟩ | M$ and exists $x$ s.t for every $y \in L (M), x y \notin L (M) .} \in .$ not RE $M^{'}$ on input x: it runs M on w; if M halts on w, $M^{'}$ accepts.
$L = {⟨ M ⟩ | M$ and exists $x, y$ s.t for every $y \in L (M), y \notin L (M) .} \in .$ Recursive (the language of all Turing machines)
$L = {⟨ M ⟩ | M$ is TM and exists $M^{'}$ s.t $M \neq M^{'}$ and $L (M) = L (M^{'}) .} \in .$ Recursive(the language of all Turing machines)
$L = {⟨ M_{1}, M_{2} ⟩ | M$ and $L (M_{1}) \leq_{m} L (M_{2})}$ not RE $\overset{―}{H T} (M, w) = ⟨ M_{1}, M_{2} ⟩ .$ s.t $L (M_{2}) = \emptyset$ . $M_{1}$ on input $y$ : run M on $w$ if M halts, check whether y is of the form $⟨ M^{'}, z ⟩$ where $M^{'}$ is TM and z is str. if so run $M^{'}$ on z. if $M^{'}$ halts, $M_{1}$ accept . hence (1)if $(M, w) \in \overset{―}{H T} \Rightarrow L (M_{1}) = \emptyset$ (2) otherwize then $L (M_{1}) = H A L T$
$L = {⟨ M_{1}, M_{2} ⟩ | M$ M does not accept any string w such that 001 is a prefix of $w}$ not RE
$L = {⟨ M ⟩ | M$ M does not accept any string w s x is a prefix of $w}$ not RE
$L = {⟨ M ⟩ | M$ x is prefix of $M}$ Recurcive
$L = {⟨ M_{1}, M_{2}, M_{3} ⟩ | L (M_{1}) = L (M_{2}) \cup L (m_{3})}$ not RE
$L = {⟨ M_{1}, M_{2}, M_{3} ⟩ | L (M_{1}) \subseteq L (M_{2}) \cup L (m_{3})}$ not RE M1 on x: runs M on w; if M halts, M1 accepts.M2 on y: reject. M3 on z: reject.
$L = {⟨ M_{1} ⟩$ there exist two TM’s M2 and M3 such that $| L (M_{1}) \subseteq L (M_{2}) \cup L (m_{3})}$ Recursive
$L = {⟨ M, w ⟩$ M is a TM that accepts w using at most $2^{|} w |$ squares of its tape $}$ Recursive Let m be the number of states in M, and k be the size of the alphabet that M uses, and $r = | w |$ if M uses at most $2^{r}$ squares of its tape, then there are at most $a = m k^{2^{r}} 2^{r}$ configurations.If M runs on w for more than $a$ steps, and does not use more than $2^{r}$ squares of its tape, then M must be in the one configuration at least twice.
$M^{'}$ runs M on w for at most a + 1 steps.If M accepts w within a steps with using at most $2^{r}$ squares, $m^{'}$ halts and accepts
Wich one is False for sure $D T I M E [n^{2}] = L$ $P = N P R L \in P$
Wich one we dont know if it close under klee star $L$ $P N P E X P$
Let $f$ be computable with circut size $| S |$ we can construct circuit size $O (S)$ with only AND,NOT gate for sure.
$L = {G | G is an undirected graph that contains no odd length cycle} \in R L, N L$ (mybe)
$L = {G, 1^{k} | G is an undirected with exactly k triangles} \in L$
$L = {ψ$ is ( always true) $} \in C o - N P$ complete
$L = {G, k | G is an undirected with exactly k diffrent SCC} \in S P A C E (\log^{2} n), P$
If we find that $S = {G, s, t dont have path between s and t} \in L$ then $L = C o - N L$
${⟨ G, s, t ⟩$

G is an directed graph, and the shortest patch between s,t $i s a t least s i z e$ |V|/2 }NL ${⟨ G, s, t ⟩$ G is an directed graph, and exsit patch between s,t $excatliy s i z e$ |V|/2 }NPC If $NTIME (n^{100}) \subseteq TIME (n^{1000})$ then $P = N P, E X P = N E X P, NSPACE (n^{50}) \subseteq SPACE (n^{500})$ $E X A C T 3 S A T = {φ \in 3 S A T :$ every clause of ϕ $h a s e x a c t l y 3 d i s t i n c t v a r i a b l e s$ } is NPC $L_{2} = {⟨ M, 1^{n} ⟩ : M is a TM and there exists a string that M accepts in n steps}$ is NPC $L = {x y z : x y^{R} z \in L}$ is regular if $L$ Recursive $L = {x y \in Σ^{*} : (x \in L) XOR (y \in L)}$ is regular regular if $L$ Recursive.

$♠$ stand for respect under logspace reduction
CVAL= ${⟨ C, x ⟩ : C is boolean circut and C (x) = 1} \in \P -$ complete $♠$
STCON= ${⟨ G, s, t ⟩ : G is a directed graph and exsit path from s to t} \in \P, N L -$ complete $♠$
UHAMPATH= ${⟨ G, s, t ⟩ : G is a undirected graph and exsit ham' path from s to t} \in N P C$
UHAMCYCLE= ${⟨ G ⟩ : G is a undirected graph has Hamiltonian cycle} \in N P C$
SUBSET-SUM= ${⟨ S = s_{1} \dots s_{k}, t ⟩ : \exists T \subseteq S, \sum_{s \in T} s = t} \in N P C$

Theorem

(extended rice) Let $C \subset R E$ s.t $Σ^{*} \notin C, C \neq \emptyset .$ then $L_{C} \notin R E$

L_{C} = {⟨ M ⟩ : M is TM and L (M) \in C} \notin R E

Proof ▼

⟨ M, w ⟩ \in \overset{―}{A C C} \Rightarrow L (B_{M, w}) = A \in C ⟨ M, w ⟩ \notin \overset{―}{A C C} \Rightarrow L (B_{M, w}) = Σ^{*} \notin C

2-NFA with same L

to compare languages accepted by both we have to figure out if L(A) is equal to L(B) or not. Thus, you have to find out if L(A)-L(B) and L(B)-L(A) is null set or not. (Reason1)
Part1: To find this out, we construct NFA X from NFA A and NFA B, . If X is empty set then L(A) = L(B) else L(A) != L(B). (Reason2)
Part2: Now, we have to find out an efficient way of proving or disproving X is empty set. When will be X empty as DFA or NFA? Answer: X will be empty when there is no path leading from starting state to any of the final state of X. We can use BFS or DFS for this. $X = (A \cap B^{'}) \cup (B \cap A^{'}) = \emptyset ?$

(a) L = {⟨ M, w ⟩ M attempts to move its head left when its head is on the leftmost tape cell}

We prove by contradiction that L is undecidable. Assume L was decidable, and let $M *$ be a TM that decides it. We construct a TM, M0 , that decides HP (the halting problem), i.e., we show HP is decidable as well, which is a contradiction. The TM M0 on input hM, wi: i. build a TM, M00 , from M, where M00 shifts w one tape cell to the right, and mark the leftmost tape cell with ]. ii. TM M00 runs M on w. iii. If M00 encounters the ] symbol during the run of M on w, then M00 moves to the right and simulates M reaching the leftmost tape cell. iv. If M halts and accepts, M00 simulates moving its head all the way to the left and off the leftmost tape cell The TM M0 runs $M *$ on the input hM0 , wi. If $M *$ accepts, M0 accepts; otherwise, M0 rejects. Notice that $M *$ always halts (accepts or rejects) since we assumed it is a decider. You can prove now that M00 moves its head off of the leftmost tape cell iff M halts (and accepts) w. It then follows that M0 decides HP, and hence HP is decidable, which is a contradiction. Therfore, the language L is not decidable.

(b) L = {⟨ M, w ⟩ M moves its head left on input w}

The trick to proving this language is decidable is to notice that M moves its head left on an input w if and only if it does so within the first $| w | + | Q | + 1$ steps of its run on w, where $| Q |$ is the number of states of the machine M. Prove it! Therefore, to decide whether an input hM, wi is an instance of L, the decider $M *$ simply runs M on w for at most $| w | + | Q | + 1$ steps and accepts iff M does moves its head left (the correctness of this construction follows immediately after you prove the validity of the above trick)

$A C C B S = {⟨ M, w, k ⟩ M is a TM that accepts w using k cells} \in R$ $b = | Q | \times | Γ |^{k} \times k$ is a bound on the number of k cell configurations of M. Any $f (n)$ space bounded Turing machine also runs in time $2^{O (f (n))}$ . Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $| Q | \cdot f (n) \cdot | Γ |^{f (n)}$ If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$ , or it loops forever. That’s because if it runs for at least $k + 1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $| Γ | = 2^{c}$ , i.e., $c = \lg | Γ |$ . Then $| Γ |^{f (n)} = (2^{c})^{f (n)} = 2^{c f (n)} = 2^{O (f (n)}$ . For similar reasons, $| Q | \cdot f (n) \cdot | Γ |^{f (n)} = 2^{O (f (n)}$ . So, the number of possible configurations of a $f (n)$ -space-bounded Turing machine is $2^{O (f (n)}$ , and thus any such machine must either halt in time at most $2^{O (f (n)}$ or loop forever.
${⟨ M ⟩ ∣ M is a Turing machine such that L (M) \in P}$ is undecidable.

{ $⟨ M ⟩ ∣ M is a Turing machine such that M \in P}$ = ${⟨ M ⟩ | (\exists k \forall x) M (x) halts in O (| x |^{k}) time}$ We reduce from the halting problem. Suppose that we are given a machine $M$ , and we are to decide whether $M$ halts on the empty input. We construct a new machine $M^{'}$ accepting a single input $x$ , which operates as follows:

1. Let $n = | x |$ . 2. $M^{'}$ runs $M$ for $n$ steps. 3. If $M$ halted within $n$ steps then $M^{'}$ runs a dummy loop taking exponential time $Ω (2^{n})$ . Otherwise, $M^{'}$ just halts.

Since Turing machines can be simulated with only polynomial overhead, if $M$ doesn’t halt then $M^{'}$ runs in polynomial time. If $M$ halts, then $M^{'}$ takes exponential time. Hence $M$ halts iff $M^{'}$ is not polynomial time.

—

More generally, this shows that even if we know that $M$ runs in time at most $f (n)$ for some superpolynomial time-constructible $f$ , then we cannot decide whether $M$ runs in polynomial time.

Proof ▼

ϕ = ⋀_{m = 1}^{n} (x_{m} \lor y_{m} \lor z_{m}) SAT \leq_{p} IndSet

with $m$ clauses, produce the graph $G_{ϕ}$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k = m$ . In our example, we have triangles on $x, y, \overset{―}{z}$ and on $\overset{―}{x}, w, z$ plus the edges $(x, \overset{―}{x})$ and $(\overset{―}{z}, z)$ .

>We need to prove two directions. First, if $ϕ$ is satisfiable, then $G_{ϕ}$ has an independent set of size at least $k$ . Secondly, if $G_{ϕ}$ has an independent set of size at least $k$ , then $ϕ$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $ϕ$ is not satisfiable, then $G_{ϕ}$ does not have an independent set of size at least k".)

>For the first direction, consider a satisfying assignment for $ϕ$ . Take one true literal from every clause, and put the corresponding graph vertex into a set $S$ . Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $ϕ$ ).

>For the other direction, take an independent set $S$ of size $k$ in $G_{ϕ}$ . Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overset{―}{x}$ , since any such pair of conflicting literals are connected by an edge in $G_{ϕ}$ ). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$ , and thereby satisfy the formula $ϕ$ .

>This reduction is polynomial in time because $\dots ?$

I’ve looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it’s being left out because it’s trivial, but that doesn’t help me when I’m trying to learn how to explain such things.

$L = {⟨ M, 1^{n} ⟩ : M is a TM and exists a string that M accepts in n steps}$ (cook-levin)
a. $L \in N P C$ The witness is a word that M accepts in at most n steps b. $L^{'} \in N P$ and let V be a verifier for $L^{'}$ of running time at most p for some polynomial p. For a string w, let $v_{w}$ be the TM that on input c, emulates $V (w, c)$ . Consider the reduction $f (w) = (⟨ V_{w}, 1^{p (| w |)} ⟩$ It is easy to verify that f is polytime computable, and that $f (w) \in L \leftrightarrow w \in L$

3-SAT: Given a CNF formula

φ

, where every clause in

φ

has *exactly* 3 literals in it, one should determine if there exist an assignment that satisfies it.
Max-2-SAT: Given a CNF formula, where every clause in

ϕ

has *exactly* 2 literals in it, and a positive number

k

, one should determine if there exist an assignment that satisfies *at least*

k

clauses.

Proof ▼

Replace a singleton clause $a$ with $a \lor b$ and many copies of $\neg b \lor c$ , $\neg b \lor \neg c$ . Reductions without extra variables don’t work even when singleton clauses are allowed. There are five types of clauses: $ℓ_{1}, \neg ℓ_{1}, ℓ_{1} \lor ℓ_{2}$ , $ℓ_{1} \lor \neg ℓ_{2}$ , $\neg ℓ_{1} \lor \neg ℓ_{2}$ . Suppose that $k$ of $ℓ_{1}, ℓ_{2}, ℓ_{2}$ are true. The probability that a random clause of each type is true is:

\begin{array}{ccccc} k & 0 & 1 & 2 & 3 \\ ℓ_{1} & 0 & 1 / 3 & 2 / 3 & 1 \\ \neg ℓ_{1} & 1 & 2 / 3 & 1 / 3 & 0 \\ ℓ_{1} \lor ℓ_{2} & 0 & 2 / 3 & 1 & 1 \\ ℓ_{1} \lor \neg ℓ_{2} & 1 & 1 / 3 & 1 / 3 & 1 \\ \neg ℓ_{1} \lor \neg ℓ_{2} & 1 & 1 & 2 / 3 & 0 \end{array}

We would like to take a convex combination of these rows which is of the form

\begin{array}{cccc} α & β & β & β \end{array}

However, all such convex combinations have $α = β$ .

3 S A T \leq_{P} exactly 1/3 SAT

Proof ▼

Let $z$ be a new variable not in $ϕ$ . Let there be $m$ clauses in $ϕ$ . We add $(z \lor \neg z)$ and $2 m + 2$ copies of $(z)$ to $ϕ$ . In every exactly 1/3-satisfying assignment $z$ must be false.

Let $ϕ \land (z \lor \neg z) \land (z) \land (z) \land . . . (2 m + 2)$ copies $. . . \land (z) = ϕ^{'}$ . The following claim is easy to prove.

Claim: $ϕ$ is satisfiable iff $ϕ^{'}$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq_{P}$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete.

1 Algorithm Definition

2 Turing Machine

2.1 Configuration

2.2 Computations

2.3 T(uring)-Computability

2.4 Poly reduction

2.5 Total Function

2.6 Partial Function

Recursion Axiom

3 Turing Machines

3.1 K-tapes Turing Machines

3.2 IO Turing Machines

3.3 Nondeterministic Turing Machines

4 Reductions

4.1 Reduction Relations

4.2 Properties

4.3 Hard and Complete Problems

Boolean Circuit

Definition

Regular language

5 Classical Results

Resulting regular expres­sion:

6 Complexity Classes

6.1 Hierarchy

Resulting regular expres­sion:

7 Theorems on Complexity of Turing Machines

Space complexity

Composition of space-bounded functions

Randomized

PP=RP consequences

change probability in definition of PP

CircuitSat ∈ DTIME(2n) consequences

P/poly =∪c∈NSIZE(nc) consequences

Prove that PP is closed under complement

Rice extended(not the version we saw)

Prove/ Disprove

8 Determine if L in P

Resulting regular expres­sion:

8.1 Examples

2-NFA with same L

Resulting regular expression:

Resulting regular expression:

$PP=RP$ consequences

CircuitSat $\in$ DTIME $(2^{n})$ consequences

P/poly $= \cup_{c \in N}$ SIZE $(n^{c})$ consequences

8 Determine if $L$ in $P$

Resulting regular expression: