5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – vzn Sep 5 '12 at 1:20
  • $\begingroup$ 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 $\endgroup$ – vzn Sep 5 '12 at 14:54
  • $\begingroup$ See arxiv.org/pdf/1104.4468v3.pdf for a (quantum) query complexity direct product theorem, and references therein. $\endgroup$ – blk Sep 5 '12 at 16:33
  • $\begingroup$ 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 $\endgroup$ – vzn Sep 8 '12 at 17:27
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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