k-SATと指数時間仮説のための希薄化補題

According to R. Impagliazzo, R. Paturi and F. Zane,
2001
an instance of $k$-SAT is called sparse if $m =
O(n)$ where $m$ denotes the number of clauses and $n$ the number of
variables. The Sparsifiction Lemma, as mentioned in
R. Impagliazzo, R. Paturi, 2001
says:

[…] that an arbitrary $k$-CNF can be expressed (in
subexponential time) as the disjunction of a subexponential number
of linear size $k$-CNFs. More precisely […]

For all $varepsilon > 0$, $k$-CNF $F$ can be written as the
disjunction of at most $2^{varepsilon n}$ $k$-CNF $F_i$ such that
$F_i$ contains each variable in at most $c(k,varepsilon)$ clauses
for some function $c$. Moreover, this reduction takes at most
$poly(n) 2^{varepsilon n}$ time.

上記の削減では、各$ k $ -CNF $ F_i $には多くとも$ c(k、
varepsilon)n個の節が多く、上記の意味では疎です。 この話によると、指数時間仮説(ETH)は次のように述べています。

$ 3 $ -SATインスタンス($ n $変数と$ m $句)は時間$ O(poly(n)2 ^
{o(n)})$で解くことができません。

($ O ^ { ast} $ –
スター表記は多項式を抑制するだけです)。そして、Sparsification補題は次のものと同等であると言います。

ETHが成り立つ場合、時間$ O(poly(n)2 ^ {o(n + m)})$で$ 3 $
-SATインスタンスを解くことはできません。

私は第二の主張を理解していないので、なぜこれが希薄化補題の陳述であるのか、誰かが説明できるのかどうか尋ねています。

ベストアンサー

私はあなたの混乱はETHの声明を誤って引用することから来るかもしれないと思います。

$ 3 $ -SATインスタンス($ n $変数と$ m $句)は、$ poly(n) cdot 2 ^ {o(n)}
$で解決できません。

このステートメントはETHではなく、弱い(しかししばしば非常に有用な)結果である。 ETHは次のように主張している。

There exists a $delta>0$ such that no algorithm with running
time $poly(m)cdot 2^{delta n}$ can solve $3$-SAT.

今度は、Sparsification Lemmaを実際に使用して、次のことを証明できます。

ETHが成り立つならば、$ 3 $ -SATインスタンスは$ poly(m) cdot 2 ^ {o(n + m)}
$で解くことができません。

Assume that there is an algorithm $A$ which solves $3$-SAT in
time $poly(m)cdot 2^{o(n+m)}$. For any $delta>0$, we’ll
construct an algorithm $B_delta$ which solves $3$-SAT in time
$poly(m)cdot 2^{delta n+o(n)}$. (This contradicts ETH and
finishes the proof.)

最初に、アルゴリズム$ B_ delta $は入力式$ phi $をとり、$ varepsilon =
delta $でSparsification補題を適用し、時間$ poly(m) cdot 2 ^ { delta n} $
produce $ ^ { delta n} $ formula $ phi_i $、 phi $は充足可能です。$
が存在する場合のみ colon phi_i $は充足可能です。ここで、アルゴリズム$ B_ delta
$は、アルゴリズム$ A $を使用して$ phi_i $を解きます。 Sparsification Lemmaによって、$
phi_i $の句の数は$ O(n)$であるので、各$ phi_i $は$ 2 ^ {o(n)} $時間で$ A
$によって解かれることに注意してください。ここで、$ B_ delta $の合計実行時間は$$ poly(m) cdot 2 ^
{ delta n} + poly(m) cdot 2 ^ { delta n} 2 ^ {o(n)} = poly(m)
cdot 2 ^ { delta n + o(n)} ; 。$$

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です