<p>Assume $C'(X)$ is a logically equivalent but minimized version of $C(X)$. Then $C'(X) \notin  SIZE(poly(X))$, unless the polynomial hierarchy collapses. </p>

<p>To see this, assume $C'(X) \in SIZE(poly(X))$, i.e. $C'(X) \in P/poly$. As noted in the original post, this would imply $NP \in P/poly$, but then the claim follows from Karp-Lipton.</p>

<p>Thus, even the <em>existence</em> of a poly-sized circuit equvialent to $C(X)$ is unlikely. Or, in turn, a generalization of direct product theorems to the dependent case appears plausible under complexity theoretic assumptions.</p>

CC BY-SA 3.0
2012-09-04T21:06:21.903Z
2012-09-04T21:06:21.903Z
blk
<p>Let $\phi(x_1,\dots,x_n)$ be a CNF. It is satisfiable if $\exists X=(x_1,\dots,x_n): \phi(X)=1$. Assume $\phi$ has a <em>unique</em> satisfying assignment. Then, by allowing only black-box queries to $\phi$, essentially $\Theta(2^n)$ queries will be required to find the satisfying $X$, i.e. to solve this <strong>NP</strong>-complete problem.</p>

<p>Now let us construct a circuit $C(X) = \bigvee_{\sigma_i \in S_n} \phi(\sigma_i(X))$, where $\bigvee$ is over all $n!$ many permutations $\sigma_i$ in the symmetric group $S_n$ of of $n$ elements. Thus, if evaluated in the trivial black-box way, $C(X)$ requires exponential time. But let us ignore this problem for a moment.</p>

<p>$C(X)$ has the nice property, that $C(X)$ has $n!$ satisfying assignment, if $\phi(x)$ has a unique one, and $C(X)$ remains unsatisfiable if $\phi(x)$ is. Essentially inputs to $C(X)$ are equivalent up to the number of $1$'s in the input. Thus testing $n+1$ different assignments with $0 \dots n$ bits set suffices to decide satisfiability of $\phi(x)$.</p>

<p>Let us now come back to the resources required to evaluate $C(X)$. Essentially $C(X)$ is solving $n!$ instances of the same problem (CNF evaluation) in parallel. There are (strong) direct product theorems which essentially say that solving $k$ <em>independent</em> instances of the same problem in parallel require essentially $k$ times the resources of solving a single instance (with non-neglible probability). But, crucially, the $n!$ instances of CNF evaluation we are solving are <strong>not</strong> <em>indepent</em>. We can walk over all permutations from one $\sigma_i$ to another $\sigma_j$ which differ only in the mapping of two variables. Thus, many clauses in $\phi(\sigma_i(X))$ and $\phi(\sigma_j(X))$ refer to the same variables and will evaluate to the same value. Thus evaluation of (large?) sets of clauses may be shared and reused while evaluating $\phi(\sigma_i(X))$ for various $i$.</p>

<p><strong>The question I have is</strong>: are there any results on the resources required for <em>dependent</em> evaluation of $k$ instances of a problem (like direct product theorems, but maybe with contrary conclusion)? What impossibility result would an approach like the above run into as it implies a (novel?) approach for solving $NP$-complete problems? Would assuming $P \neq NP$ already imply a lower-bound on the <em>dependent</em> evaluation problem of $k$-instances, i.e. a generalization of direct product theorems?</p>

<p><strong>EDIT:</strong> The problem appears to be a special case of the <em>OR(SAT)-problem</em> where one is given a set of SAT-instances $\psi_1, \dots, \psi_t$ and is aked to decide $\psi = \bigvee_{i=1}^t \psi_t$. The related <em>instance compression</em> problem asks for a reduction of $\psi$ to a much smaller instance $\psi'$. See <a href="http://eccc.hpi-web.de/report/2012/112/" rel="nofollow">this paper</a> by Drucker for details and (references to) negative results on the problem. Thus, the minimized circuit $C'(X)$ in the answer below is an exponentially compressed instance of an OR(SAT)-problem, where the $\psi_i$ are equivalent to a single CNF $\phi$ up to relabeling of the input variables and the complete set of all possible relablings.</p>

CC BY-SA 3.0
2012-09-05T01:20:22.760Z
something to look into-- pigeonhole proofs of SAT that show they require exponential size resolution proofs, and also razborov style proofs of exponential monotone circuit size for NP complete problems (mainly Clique detection).
vzn
CC BY-SA 3.0
2012-09-05T14:54:37.050Z
can you cite a ref on the direct product thms you're referring to? another way to view this is that for many NP complete problems there are reorderings/permutations of the inputs that give an equivalent problem. SAT/graph problems are examples of this. for graph problems, its isomorphism. for SAT, reordering of variables/clauses. some of this is handled in SAT by focusing on NP complete 3-SAT. its a kind of recurring symmetry across problems. which seems related to the [isomorphism conjecture](http://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html)
vzn
CC BY-SA 3.0
2012-09-05T16:33:24.320Z
See http://arxiv.org/pdf/1104.4468v3.pdf for a (quantum) query complexity direct product theorem, and references therein.
blk
CC BY-SA 3.0
2012-09-08T17:27:36.150Z
thx for the ref, interesting. it would appear to be an idea to attack P vs NP via QM complexity directions which does seem to have some new perspective/angle, particularly wrt reversibility, not often considered in CS, ie more often disregarded, itself a kind of symmetry. re symmetry in NP complete problems, see also on here eg [relations between symmetry and computational intractability](http://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability)
vzn
<cc.complexity-theory>
Are resource savings for the evaluation of $k$ dependent instances in parallel possible?
blk
# Are resource savings for the evaluation of $k$ dependent instances in parallel possible?

(Asked by: username_0 on 2012-09-04)

Let $\phi(x\_1,\dots,x\_n)$ be a CNF. It is satisfiable if $\exists X=(x\_1,\dots,x\_n): \phi(X)=1$. Assume $\phi$ has a *unique* satisfying assignment. Then, by allowing only black-box queries to $\phi$, essentially $\Theta(2^n)$ queries will be required to find the satisfying $X$, i.e. to solve this **NP**-complete problem.

Now let us construct a circuit $C(X) = \bigvee\_{\sigma\_i \in S\_n} \phi(\sigma\_i(X))$, where $\bigvee$ is over all $n!$ many permutations $\sigma\_i$ in the symmetric group $S\_n$ of of $n$ elements. Thus, if evaluated in the trivial black-box way, $C(X)$ requires exponential time. But let us ignore this problem for a moment.

$C(X)$ has the nice property, that $C(X)$ has $n!$ satisfying assignment, if $\phi(x)$ has a unique one, and $C(X)$ remains unsatisfiable if $\phi(x)$ is. Essentially inputs to $C(X)$ are equivalent up to the number of $1$'s in the input. Thus testing $n+1$ different assignments with $0 \dots n$ bits set suffices to decide satisfiability of $\phi(x)$.

Let us now come back to the resources required to evaluate $C(X)$. Essentially $C(X)$ is solving $n!$ instances of the same problem (CNF evaluation) in parallel. There are (strong) direct product theorems which essentially say that solving $k$ *independent* instances of the same problem in parallel require essentially $k$ times the resources of solving a single instance (with non-neglible probability). But, crucially, the $n!$ instances of CNF evaluation we are solving are **not** *indepent*. We can walk over all permutations from one $\sigma\_i$ to another $\sigma\_j$ which differ only in the mapping of two variables. Thus, many clauses in $\phi(\sigma\_i(X))$ and $\phi(\sigma\_j(X))$ refer to the same variables and will evaluate to the same value. Thus evaluation of (large?) sets of clauses may be shared and reused while evaluating $\phi(\sigma\_i(X))$ for various $i$.

**The question I have is**: are there any results on the resources required for *dependent* evaluation of $k$ instances of a problem (like direct product theorems, but maybe with contrary conclusion)? What impossibility result would an approach like the above run into as it implies a (novel?) approach for solving $NP$-complete problems? Would assuming $P \neq NP$ already imply a lower-bound on the *dependent* evaluation problem of $k$-instances, i.e. a generalization of direct product theorems?

**EDIT:** The problem appears to be a special case of the *OR(SAT)-problem* where one is given a set of SAT-instances $\psi\_1, \dots, \psi\_t$ and is aked to decide $\psi = \bigvee\_{i=1}^t \psi\_t$. The related *instance compression* problem asks for a reduction of $\psi$ to a much smaller instance $\psi'$. See [this paper](http://eccc.hpi-web.de/report/2012/112/) by Drucker for details and (references to) negative results on the problem. Thus, the minimized circuit $C'(X)$ in the answer below is an exponentially compressed instance of an OR(SAT)-problem, where the $\psi\_i$ are equivalent to a single CNF $\phi$ up to relabeling of the input variables and the complete set of all possible relablings.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: something to look into-- pigeonhole proofs of SAT that show they require exponential size resolution proofs, and also razborov style proofs of exponential monotone circuit size for NP complete problems (mainly Clique detection).  
> **username_1**: can you cite a ref on the direct product thms you're referring to? another way to view this is that for many NP complete problems there are reorderings/permutations of the inputs that give an equivalent problem. SAT/graph problems are examples of this. for graph problems, its isomorphism. for SAT, reordering of variables/clauses. some of this is handled in SAT by focusing on NP complete 3-SAT. its a kind of recurring symmetry across problems. which seems related to the [isomorphism conjecture](http://blog.computationalcomplexity.org/2003/03/berman-hartmanis-isomorphism.html)  
> **username_0**: See http://arxiv.org/pdf/1104.4468v3.pdf for a (quantum) query complexity direct product theorem, and references therein.  
> **username_1**: thx for the ref, interesting. it would appear to be an idea to attack P vs NP via QM complexity directions which does seem to have some new perspective/angle, particularly wrt reversibility, not often considered in CS, ie more often disregarded, itself a kind of symmetry. re symmetry in NP complete problems, see also on here eg [relations between symmetry and computational intractability](http://cstheory.stackexchange.com/questions/871/relationship-between-symmetry-and-computational-intractability)  

---

## 1 answers

### Answer by username_0 on 2012-09-04. Score: 2

Assume $C'(X)$ is a logically equivalent but minimized version of $C(X)$. Then $C'(X) \notin SIZE(poly(X))$, unless the polynomial hierarchy collapses.

To see this, assume $C'(X) \in SIZE(poly(X))$, i.e. $C'(X) \in P/poly$. As noted in the original post, this would imply $NP \in P/poly$, but then the claim follows from Karp-Lipton.

Thus, even the *existence* of a poly-sized circuit equvialent to $C(X)$ is unlikely. Or, in turn, a generalization of direct product theorems to the dependent case appears plausible under complexity theoretic assumptions.


---

