# EX 1: Unary languages

## 1.

Assume

U ≝ \lbrace 1^n \mid ⋯ \rbrace ∈ NP-complete

We have

SAT ≼_{\bf L} U

There’s a reduction $R$ s.t.:

φ \text{ SAT } ⟺ R(φ) ∈ U

So if $t∈ \lbrace 0, 1 \rbrace^\ast$ is a partial valuation

• $φ(t)$ an evaluation of $φ$, we have $2^{\vert φ \vert}$ possible values

And as $U ∈ NP$:

\vert R(φ) \vert ≤ p(\vert φ \vert)
• $R(φ(t))$, we have $p(\vert φ \vert)$ possible values
R(φ(t)) = R(φ(t')) ⟺ ∨ \begin{cases} φ(t) ∈ SAT ∧ φ(t') ∈ SAT \\ φ(t) ∉ SAT ∧ φ(t') ∉ SAT \end{cases}
SAT(φ, t):
if |t| = |φ|:
if φ(t) has no clauses: YES
else: NO
else:
SAT(φ, t0) ∨ SAT(φ, t1)


On SAT(φ, ε), $2^{\vert φ \vert}$ calls.

We store a hashtable $h$ of all the $R(φ(t’))$ computed, and then we compare $R(φ(t))$ with the previous values to know if the value of $φ(t)$ is the same of a previous value

SAT(φ, t):
if h(R(φ(t)))≠-1: # already in stored
then return h(R(φ(t)))
else:
u = SAT(φ(t0))
h(R(φ(t0))) = u
v = SAT(φ(t1))
h(R(φ(t1))) = v
return u ∨ v


We use $R$ as a hashtable ⟶ $O(p × p_R)$ space used

## 2.

NEXP \overset{?}{⊆} EXP

Assume for all unary language $U ∈ NP$, $U ∈ P$.

Let $L ∈ NEXP$ recognized by $ℳ$, running in $t(\vert x \vert)$ time.

Turn $L$ into a unary language $\tilde{L} ∈ NP$.

We have a way to encode $x$ into $1^{t(x) + 2^{\vert x \vert}}$

\tilde{L} ≝ \lbrace 1^{t(x) + 2^{\vert x \vert}} \mid x ∈L \rbrace

$ℳ’$ =

• on input $1^y$:

• guess an $x$ such that $y = t(x) + \underbrace{2^{\vert x \vert}}_{∈ NP}$
• run $ℳ$ on $x$: takes time $t(\vert x \vert) = O(2^{\vert x \vert}) = O(1^{t(x) + 2^{\vert x \vert}})$

Thus with the assumption:

∃ℳ'', ℳ'' ∈ P, \text{ and } ℳ'' \text{ recognizes } \tilde{L}

$𝕄$, running in polynomial time, recognizing $L$

$𝕄$ on input $x$:

• compute $2^{\vert x \vert}, t(x)$
• write $1^{2^{\vert x\vert} + t(x)}$
• simulate $ℳ’’$

exptime in $p(1^{t(x) + 2^{\vert x \vert}}) = \exp(\vert x \vert)$

$𝕄$ runs in exptime, and recognizes $L$.

So $L ∈ Exptime$

# EX 2: One-way functions

• $f: \lbrace 0, 1 \rbrace^k ⟶ \lbrace 0, 1 \rbrace^k ∈ P$
• $f^{-1} ∉ P$
A ≝ \lbrace (x,y) \mid f^{-1}(x)<y \rbrace

$NP$:

$ℳ$:

• input $x, y$
• guess $z$ s.t. $f(z) = x$
• return $z < y$

$coNP$:

$co$-$ℳ$:

• input $x, y$
• guess $z$ s.t. $f(z) = x$
• return $z ≤ y$

Assume $A ∈P$

$ℳ’$

• input $x$
• $v = 2^k -1$
• $(x, v) ∈ A$
• if true:
• $v = ⋯$

Dichotomic search: $∈ \log(2^k) ⟶ O(k)$: it’s $P$

# EX 3: Prime Numbers

## 1.

UNARY\text{-}PRIME ≝ \lbrace 1^n \mid n \text{ is a prime number} \rbrace
for i = 1 to sqrt(n):
if i|n:
return "not prime"
return "prime"


in $O(p^2)$

## 2.

Prime ≝ \lbrace p \mid p \text{ is prime} \rbrace
n ∉ ℙ ⟹ ∃ d∈ℕ; d≠n, 1; d\mid n

## 3.

Guess $a$

run the algo

• Compute $a^k \mod φ$: $\log k$ multiplications
• How many computations? $\underbrace{(q+1)}_{≤ O(\log p)}$ times

Best one: AKS (in P)

# EX 4: Some P-complete problems

## 1.

$𝒫$:

• input: a set $X$, a binary operator $\ast$ defined on $X$, a subset $S ⊆ X$, and $x ∈ X$
• output: does $x ∈ \overline{S}$, where $\overline{S}$ is the transitive closure (for $\ast$) of $S$

$𝒫 ∈P$ (simple propagation)

Now P-hardness:

Reduction from MCV:

MCV ≼ 𝒫

Let $𝒞 ≝ (V, E, l)$ be a MCV.

We will assume that every node in the circuit has at most 2 predecessors.

We want

v(⋯) = ⊥ \text{ ( or } ⊥ \text{ ) } ⟺ ⋯ ∈ \overline{S}
• X ≝ \lbrace v^0, v^1 \mid v ∈ V \rbrace
• S ≝ \lbrace x^0 \mid x ∈ V, x \text{ is a leaf and } l(x) = ⊥\rbrace ∪ \lbrace x^1 \mid x ∈ V, x \text{ is a leaf and } l(x) = ⊤\rbrace
x^i \ast y^j ≝ w^{i l(w) j} \text{ if } (x, w)∈E, (y, w)∈E

Therefore:

∀t∈V, v(t) = a ⟺ t^a ∈ \overline{S} \qquad \text{ if } a ∈ \lbrace 0, 1 \rbrace

## 2.

Membership:

• input: $G$ a context-free grammar, $w$ a word
• output: does $w ∈ L(G)$

P-hardness:

𝒫 ≼ Membership

with the previous problem $𝒫$

Given $(X, x, S, \ast)$, give

G ≝ (S, T, V, P) \text{ and } w

Let

• $w ≝ ε$
• $V ≝ X$
• $S ≝ \lbrace x \rbrace$
• $T = ∅$
1. for all $x \ast y = w$, $w ⟶ xy ∈ P$
2. $x ⟶ ε$ if $x ∈ S$
x ∈ \overline{S} ⟺ ε ∈ L(G)

Tags:

Updated: