5

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

blk
  • 151
  • 5
  • 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). – vzn Sep 05 '12 at 01:20
  • 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 – vzn Sep 05 '12 at 14:54
  • See http://arxiv.org/pdf/1104.4468v3.pdf for a (quantum) query complexity direct product theorem, and references therein. – blk Sep 05 '12 at 16:33
  • 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 – vzn Sep 08 '12 at 17:27

1 Answers1

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.

blk
  • 151
  • 5