13
$\begingroup$

According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur complexity of k-TAUT are false". However, that paper only cites a personal communication.

How is the MA version of SETH proven to be false?

I suspect that it involves algebrizing the formula, but do not have any further idea.

$\endgroup$
  • $\begingroup$ Could you post the document if you get a response? $\endgroup$ – user34945 Nov 10 '15 at 16:45
  • 13
    $\begingroup$ A paper is coming soon. Thanks for your patience. $\endgroup$ – Ryan Williams Nov 10 '15 at 17:11
  • 3
    $\begingroup$ Actually I will say that what I prove is much stronger than: "there is a $1.9^n$ time Merlin-Arthur protocol for refuting k-TAUT", i.e., unsatisfiable k-CNF formulas. You can get about $2^{n/2}$ time for refuting any UNSAT circuit of sublinear depth, as far as I can tell. But as I said, the paper is coming soon. $\endgroup$ – Ryan Williams Nov 10 '15 at 22:14
  • 2
    $\begingroup$ Possibly silly question, is that result (essentially) moving towards the idea: the conjectures "NSETH" and "k-TAUT requires exponential size circuits" are mutually exclusive? Or does the PRG construction easily eat up any potential gap between the MA and NP complexity of k-TAUT? $\endgroup$ – Joe Bebel Nov 11 '15 at 9:42
  • 2
    $\begingroup$ Not a silly question! Short answer is that I don't know yet. $\endgroup$ – Ryan Williams Nov 12 '15 at 1:48
21
$\begingroup$

You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/

EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field elements, in time about $(s + 2^k) \cdot d$, where $s$ is the size of $C$ and $d$ is the degree of the polynomial computed by $C$. (We call this a "short non-interactive proof of batch evaluation" --- evaluating $C$ on many assignments.)

Then Merlin can solve $\#$SAT for Arthur as follows. Given a CNF $F$ on $n$ variables and $m$ clauses, Merlin and Arthur first construct an arithmetic circuit $C$ on $n/2$ variables of degree at most $mn$, size about $mn \cdot 2^{n/2}$, which takes a sum over all assignments to the first $n/2$ variables of the CNF $F$ (adding a $1$ to the sum when $F$ is true, and $0$ when it's false). Using the batch evaluation protocol, Merlin can then prove that $C$ takes on $2^{n/2}$ particular values on all its $2^{n/2}$ Boolean assignments, in about $2^{n/2} poly(n,m)$ time. Summing up all those values, we get the count of the SAT assignments to $F$.

Now we say at a high level how to do the batch evaluation protocol. We want the proof to be a succinct representation of the circuit $C$ that is both easy to evaluate on all of the $2^k$ given inputs, and also easy to verify with randomness. We set the proof to be a univariate polynomial $Q(x)$ defined over a sufficiently large extension field of the base field $K$ (of characteristic at least $2^n$ for our application), where $Q(x)$ has degree about $2^k \cdot d$, and $Q$ ``sketches'' the evaluation of the degree-$d$ arithmetic circuit $C$ over all $2^k$ assignments. The polynomial $Q$ satisfies two conflicting conditions:

  • The verifier can use the sketch $Q$ to efficiently produce the truth table of $C$. In particular, for some explicitly known $\alpha_i$ from the extension of $K$, we want $(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$, where $a_i$ is the $i$th Boolean assignment to the $k$ variables of $C$ (under some ordering on assignments).

  • The verifier can check that $Q$ is a faithful representation of $C$'s behavior on all $2^k$ Boolean assignments, in about $2^k + s$ time, with randomness. This basically becomes a univariate polynomial identity test.

The construction of $Q$ uses an interpolation trick originating from the holographic proofs, where multivariate expressions can be efficiently ``expressed'' as univariate ones. Both of the two items utilize fast algorithms for manipulating univariate polynomials.

$\endgroup$
  • $\begingroup$ In the centered portion (near the top) of part 2 on page 6, it looks like R(x) should be replaced with R(r). ​ ​ $\endgroup$ – user6973 Jan 20 '16 at 5:46
  • $\begingroup$ Please send comments on the manuscript to me directly; I don't check stackexchange every day. Thanks. $\endgroup$ – Ryan Williams Jan 20 '16 at 8:06
  • 5
    $\begingroup$ Could you summarize the main idea of the paper, in order to provide a more self contained answer, and possibly protect against bit-rot? $\endgroup$ – cody Jan 21 '16 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy