11
$\begingroup$

In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, and here is one such attempt.)

Question 1:

Consider a circuit for solving SAT for a formula with n variables. (Or for finding Hamiltonian cycle for a graph with $n$ edges.)

Suppose that every gate allows the computation of an arbitrary Boolean function on $m$ variables. For concreteness let’s take $m=0.6 n$.

The Strong exponential time hypothesis (SETH) asserts that even with such strong gates we need superpolynomial circuit size. In fact, we need size at least $\Omega (2^{(0.4-\epsilon) n})$ for every $\epsilon.$ In a sense, gates on fraction of the variables that represent very complicated Boolean functions (much beyond NP-completeness) do not give you much advantage.

We can further ask:

(i) Can we have such a circuit of size $2^{0.9 n}$? $2^{(1-\epsilon)n}$?

A “no” answer will be a vast strengthening of the SETH . Of course, maybe there is an easy “Yes” answer, that I simply miss.

(ii) If the answer to (i) is YES, do gates that computes arbitrary Boolean functions give some advantages compared to gates which “just” compute (say) arbitrary NP functions; or just smaller instances of SAT itself ?

The next question attempts to ask something similar for questions in $P$.

Question 2:

As before let $m< n$ and for concreteness put $m=0.6n$. (Other values of $m$ such as $m=n^\alpha$ are also of interest.) Consider the following types of circuits:

a) In one step you can compute an arbitrary Boolean function on $m$ variables.

b) In one step you can solve a SAT problems with $m$ variables. Or perhaps an arbitrary nondeterministic circuit of polynomial size in $m$ variables.

c) In one step you can perform an arbitrary circuit on $m$ variables of size $m^d$ ($d$ is fixed).

d) In one step you can perform ordinary Boolean gates.

Let us consider the question of finding a perfect matching for a graph with $n$ edges. Matching has a polynomial size circuit. The question is if the exponent in such a matching algorithm can be improved when you move from circuits of type d) to circuits of type c), and from circuits of size c) to circuits of size b), and from circuits of size b) to circuits of size a).

(This may be related to well-known issues about parallel computation or about oracles.)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Actually the Strong ETH is not that strong: it just says you can't have a uniform algorithm running in $O(1.9999^n)$ time for SAT with $cn$ clauses, for all $c$. Allowing arbitrary Boolean functions on small sets of variables puts you in nonuniform circuit land. The "nonuniform SETH" is an interesting variant but I don't think it's been studied too closely yet. $\endgroup$
    – Ryan Williams
    Aug 12, 2015 at 7:35
  • $\begingroup$ Dear Rayan, right, I just feel more comfortable to consider the non-uniform case. A no answer to Question 1 will be a vast strengthening of the nonuniform SETH. (I thought that nonuniform SETH as a strengthening of SETH, but maybe I was wrong.) Possibly you can reformulate Questions 1 and 2 for uniform algorithms. In any case perhaps with such strong versions of SETH and non-uniform SETH it will be possible to find a counterexample. $\endgroup$
    – Gil Kalai
    Aug 12, 2015 at 8:41
  • $\begingroup$ I guess you want to be careful about what $n$ is: in SETH it denotes the number of variables, in the above it seems to denote the input length. If you allow gates that can "compute SAT on $.1n$ variable instances" it is trivial to get a depth-2 $2^{.9n}$ size circuit for $n$ variable SAT: take an OR over all possible assignments to $.9n$ variables, and use your SAT gates to solve SAT on the remaining $.1n$ variables. But this is probably not what you're looking for.... Is it? $\endgroup$
    – Ryan Williams
    Aug 15, 2015 at 3:34

1 Answer 1

Reset to default
4
$\begingroup$

By counting you should be able to compute about $2^{2^m \cdot s}$ functions with such circuits of size $s$ so I'd guess $s=2^{n-m}$ should be enough to compute all functions.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hi, @Boaz Barak. Would you mind if I merged your two accounts on this site? $\endgroup$
    – Lev Reyzin ♦
    Nov 2, 2017 at 13:57
  • 1
    $\begingroup$ Thanks Boaz. I guess the spirit of the question is this: If you go well below what is needed to compute all function can you still compute an NP complete function. $\endgroup$
    – Gil Kalai
    Nov 2, 2017 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.