# 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: