<p>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. </p>

CC BY-SA 3.0
2017-11-02T13:57:52.523Z
Hi, @Boaz Barak. Would you mind if I merged your two accounts on this site?
Lev Reyzin
CC BY-SA 3.0
2017-11-02T16:25:38.170Z
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.
Gil Kalai
CC BY-SA 3.0
2017-11-02T03:47:06.123Z
2017-11-02T03:47:06.123Z
Boaz Barak
<p>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.)</p>
<h2><strong>Question 1:</strong></h2>
<p>Consider a circuit for solving SAT for a formula with n variables. (Or for finding Hamiltonian cycle for a graph with <span class="math-container">$n$</span> edges.)</p>
<p>Suppose that every gate allows the computation of an arbitrary Boolean function on <span class="math-container">$m$</span> variables. For concreteness let’s take <span class="math-container">$m=0.6 n$</span>.</p>
<p>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 <span class="math-container">$\Omega (2^{(0.4-\epsilon) n})$</span> for every <span class="math-container">$\epsilon.$</span> 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.</p>
<p>We can further ask:</p>
<p><strong>(i)</strong> Can we have such a circuit of size <span class="math-container">$2^{0.9 n}$</span>? <span class="math-container">$2^{(1-\epsilon)n}$</span>?</p>
<p>A “no” answer will be a vast strengthening of the SETH . Of course, maybe there is an easy “Yes” answer, that I simply miss.</p>
<p><strong>(ii)</strong> 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 ?</p>
<p>The next question attempts to ask something similar for questions in <span class="math-container">$P$</span>.</p>
<h2>Question 2:</h2>
<p>As before let <span class="math-container">$m&lt; n$</span> and for concreteness put <span class="math-container">$m=0.6n$</span>. (Other values of <span class="math-container">$m$</span> such as <span class="math-container">$m=n^\alpha$</span> are also of interest.) Consider the following types of circuits:</p>
<p>a) In one step you can compute an arbitrary Boolean function on <span class="math-container">$m$</span> variables.</p>
<p>b) In one step you can solve a SAT problems with <span class="math-container">$m$</span> variables. Or perhaps an arbitrary nondeterministic circuit of polynomial size in <span class="math-container">$m$</span> variables.</p>
<p>c) In one step you can perform an arbitrary circuit on <span class="math-container">$m$</span> variables of size <span class="math-container">$m^d$</span> (<span class="math-container">$d$</span> is fixed).</p>
<p>d) In one step you can perform ordinary Boolean gates.</p>
<p>Let us consider the question of finding a perfect matching for a graph with <span class="math-container">$n$</span> 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).</p>
<p>(This may be related to well-known issues about parallel computation or about oracles.)</p>

CC BY-SA 3.0
2015-08-12T07:35:30.617Z
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.
Ryan Williams
CC BY-SA 3.0
2015-08-12T08:41:59.980Z
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.
Gil Kalai
CC BY-SA 3.0
2015-08-15T03:34:06.483Z
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?
Ryan Williams
<cc.complexity-theory><dc.parallel-comp>
To what extent, computational ability for hard tasks helps in solving easy tasks
Gil Kalai
# To what extent, computational ability for hard tasks helps in solving easy tasks

(Asked by: username_0 on 2015-08-10)

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.)

**Tags:** cc.complexity-theory, dc.parallel-comp
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2017-11-02. Score: 4

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.

> **Comments:**
> **username_3**: Hi, @Boaz Barak. Would you mind if I merged your two accounts on this site?  
> **username_0**: 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.  

---

