Exercises 5: Prime Numbers, P-complete problems

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)\]

Leave a comment