26
$\begingroup$

For a 3CNF formula $C$ let $M(C)$ be the maximal number of satisfied clauses in any assignment to $C$. It is known that Max-3SAT is hard to approximate (subject to P≠NP), i.e. there is no polytime algorithm whose input is a 3CNF formula $C$, and whose output is the number $M'$ such that $M(C)$ is within a multiplicative factor $1+c$ from $M'$, where $c>0$ is an absolute positive constant.

I believe that it is also NP-hard to compute $M(C) \bmod p$ for any constant modulus $p$. I wonder if the following common generalization of these two facts is true: There is no polytime algorithm whose input is a 3CNF formula $C$ with $N$ clauses, and a string of $\log_2 N-B$ advice bits, and whose output is $M(C)$. Here $B$ is an absolute constant. In plain words, there is no algorithm that computes $B$ bits of information of $M(C)$.

I apologize if the question has a well-known answer, for I am not a complexity theorist by the way of background.

$\endgroup$
9
  • 1
    $\begingroup$ Usually an “advice” can only depend on the length of the input. I believe that your intent is that an “advice” here can depend on the input itself. I do not know a standard terminology for this notion. $\endgroup$ Feb 2 '11 at 19:03
  • 9
    $\begingroup$ It's a very interesting question. To confirm that $M(C)\bmod p$ is indeed hard to compute, one can note that the proof of Cook's theorem produces an $m$-variable formula $F$ that is either satisfiable or such that $M(F) = m-1$. $\endgroup$ Feb 2 '11 at 20:05
  • 16
    $\begingroup$ The question can be restated in the following way: can there be a polynomial time algorithm that, given a 3CNF formula $F$ with $m$ variables, outputs a list of $m/2^B$ numbers such that one of those number is $M(F)$? $\endgroup$ Feb 2 '11 at 20:07
  • 2
    $\begingroup$ yes, $m$ should have been the number of clauses in the above comment. $\endgroup$ Feb 2 '11 at 21:55
  • 9
    $\begingroup$ it's equivalent because if you have an algorithm as described in the post, then you can run the algorithm on each of the $2^{\log_2 m - B} = m/2^B$ possible advice string, get as many (or fewer if there are collisions) answers, and one of them is correct. If you have an algorithm as in my comment above, $\log_2 m - B$ advice bits are sufficient to specify that the correct answer is the $i$-th largest of the outputs of the algorithm, for some $i$. $\endgroup$ Feb 2 '11 at 21:57
14
$\begingroup$

Here is an argument that if you could solve Max 3SAT on an m-clause instance given a constant number of bits of advice, then the polynomial hierarchy would collapse.

Fix an NP-complete problem L. From Cook's theorem, we know a transformation f() of inputs x for L into 3SAT formulas f(x), so that

1) if $x\in L$ then $M(f(x)) = m$

2) if $x\in L$ then $M(f(x)) = m-1$

where $m$ is the number of clauses in $f(x)$.

We also have a theorem of Kadin, that says that, if given $k$ inputs $x_1,\ldots,x_k$ of an NP-complete problem, you have a polynomial time algorithm that makes $\leq k-1$ queries to an NP oracle and determines the correct answer to the $k$ NP problems $x_i \in ? L$, then the polynomial hierarchy collapses.

Suppose we have an algorithm that solves Max SAT on m-clause inputs given k bits of advice. We will use Hastad's result to construct an algorithm as in the premise of Kadin's theorem.

Start from the $K=2^k+1$ inputs $x_1,\ldots,x_K$ to problem $L$. Apply Cook's theorem to each of them. After some normalization (which can be done by assigning weights to the clauses, or duplicating them if we do not want to use weights), we construct $K$ formulas $F_1,\ldots,F_K$ where, for a certain $m$:

1) $M(F_1)= m-1$ if $x_1 \in L$ and $M(F_1) = m-2$ otherwise

2) $M(F_2) = m\cdot (m-1)$ if $x_2 \in L$ and $M(F_2) = m\cdot (m-2)$ otherwise

...

k) $M(F_K) = m^{K-1} \cdot (m-1)$ if $x_K\in L$ and $M(F_K) = m^{K-1} \cdot (m-2)$ otherwise

Now take the union of the formulas, which were constructed over disjoint variables sets, and call it $F$. So we have $M(F) = M(F_1) + \cdots + M(F_k)$, and we can "read off" the answer to the $K$ problems $x_i \in? L$ by looking at the base-$m$ representation of $M(F)$. If we can compute $M(F)$ given $k$ bits of advice, it means that we can find $2^k$ values such that one of them is $M(F)$. We can then ask non-adaptively an NP oracle whether $M(F) \geq n_i$ for each of the candidate values $n_1,\ldots,n_{2^k}$ we generated. So we have been able to solve $2^k+1$ instances of NP-complete problems by making $2^k$ non-adaptive queries to an NP oracle, which implies that the polynomial hierarchy collapses.

Using Hastad's theorem instead of Cook's theorem, it's possible to push the size of $F$ to $O(1)^k \cdot m$ instead of $m^k$, so it's possible to push $k$ to $\log m$, and the number of advice bits to $\log\log m$. Understanding what happens when you are given $\log m - O(1)$ advice bits seems really difficult.


Edited to add: Krentel (The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509 (1988)) proved that computing the value of the optimum of the maximum clique problem is complete for $FP^{NP[O(log n)]}$, the class of functions computable in polynomial time with $O(log n)$ queries to an NP oracle. The completeness is under "one query reductions," in which function f is reducible to function g if one can write $f(x) = r_1(g(r_2(x))$ for polynomial time computable $r_1$ and $r_2$. Presumably the same is true for Max Clique. Now, if Max Clique had a polynomial time algorithm that produces a list of $m^{o(1)}$ possible values, it would be in $FP^{NP[o(logn)]}$, because you could use binary search to find the optimum with a number of queries that is log of the list size.

Now, if we have $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ we would definitely have $P^{NP[O(log n)]} = P^{NP[o(log n)]}$, which is the special case for decision problems, and that is known, by results of Wagner (improving a result of Kadin that applies to a constant number of queries), to collapse the polynomial hierarchy. But I think that it might be known that $FP^{NP[O(log n)]} = FP^{NP[o(log n)]}$ would actually imply P=NP. But in any case the results of Krentel and Kadin-Wagner should be enough to give another proof of Andy Drucker's result. Now I wonder if it is actually the same proof, that is, if the Fortnow-Van Melkebeek result works, explicitly or implicitly, via a "simulating NP queries with fewer NP queries" argument.

A good survey paper that explains what is going on with optimization problems and bounded query classes:

http://www.csee.umbc.edu/~chang/papers/bqabh/npfsat.pdf

$\endgroup$
8
$\begingroup$

I would like to state one reason why proving the NP-hardness of this problem is difficult.

In a comment on the question, Luca Trevisan gave a nice way to restate the problem: Is the following problem solvable in polynomial time for every constant k? Given a CNF formula C with m clauses, output at most m/k integers so that one of them is equal to M(C). Here k is related to B by k=2B.

However, let’s demand more. Namely, we consider the following problem: given a CNF formula C, output two integers so that one of them is equal to M(C). We denote this problem by Π. The problem Π is at least as difficult as the original problem, so if the original problem is NP-hard, Π must also be NP-hard.

Note that Π is a relation problem. One of the simplest kinds of reductions that can be used to reduce some problem L to a relation problem Π is a polynomial-time Levin reduction, which is a special case of a polynomial-time Turing reduction where the reduction calls the oracle for Π only once.

We claim that PΠ[1]=P. This obviously implies that NP⊈PΠ[1] unless P=NP, that is, Π is not NP-hard under polynomial-time Levin reducibility unless P=NP.

Proof. Let L∈PΠ[1], or in other words, there exists a Levin reduction from L to Π. This means that there exists a pair (f, g) of a polynomial-time computable function f: {0,1}*→{0,1}* which maps each instance x of the problem L to some CNF formula f(x) and a polynomial-time computable predicate g: {0,1}*×ℕ×ℕ→{0,1} such that g(x, i, j) = L(x) if either i or j is equal to M(f(x)). (Here L(x)=1 if x is a yes-instance of L and L(x)=0 if x is a no-instance.)

We construct a polynomial-time algorithm for L from this as follows. Let x be an input.

  1. Let C=f(x), and let m be the number of clauses in C.
  2. Find one i ∈ {0,…,m} such that the value g(x, i, j) is constant independent of j ∈ {0,…,m}.
  3. Output this constant g(x, i, 0).

In the step 2, such i always exists because i=M(f(x)) satisfies the condition. Moreover, this algorithm cannot output a wrong answer because g(x, i, M(f(x))) must be the correct answer. Therefore, this algorithm solves L correctly. QED.

If I am not mistaken, the same idea can be used to prove that PΠ[k(n)]⊆DTIME[nO(k(n))]. This implies that NP⊈PΠ[k] for any constant k unless P=NP and that NP⊈PΠ[polylog] unless NP⊆DTIME[2polylog]. However, this idea alone does not seem to rule out the possibility that Π is NP-hard under polynomial-time Turing reducibility.

$\endgroup$
2
  • 1
    $\begingroup$ Could you provide a link to Dana's answer? $\endgroup$ Feb 4 '11 at 12:53
  • $\begingroup$ @turkistany: She had deleted her answer after I posted the first revision of this answer. I have just removed a reference to it from this answer. $\endgroup$ Feb 4 '11 at 20:02
8
$\begingroup$

I believe that we can show:

Claim. There's a value $0 < c < 1$ such that the following is true. Suppose there's a deterministic poly-time algorithm that, given an $m$-clause 3-SAT instance $\phi$, outputs a list $S$ of at most $m^c$ values, such that $M(\phi) \in S$; then the polynomial hierarchy collapses.

The proof uses Fortnow and Santhanam's results on infeasibility of instance compression from their paper http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf

Specifically, by looking at their proof of Thm 3.1, I believe one can extract the following (I will re-check this soon):

"Theorem" [FS]. There are integers $0 < d' < d$ such that the following is true. Suppose in deterministic poly-time, one can transform an OR of $n^d$ Boolean formulas (each of length $\leq n$, and on disjoint variable-sets) into an OR of $n^{d'}$ formulas (again variable-disjoint and of length $\leq n$), preserving satisfiability/unsatisfiability of the OR. Then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$ and the polynomial hierarchy collapses.

The proof of our claim will be a reduction from the OR-compression task mentioned in the above theorem[FS], to the problem of list-computing $M(\phi)$. Suppose $\psi_1, \ldots, \psi_{n^d}$ is a list of formulas whose OR we want to compress.

First step: define a polynomial-size circuit $\Gamma$ on input strings $(v, y_1, \ldots, y_{n^d})$. Here the string $y_i$ encodes an assignment to $\psi_i$, and $v \in \{0, 1\}^{d \log n + 1}$ encodes a number between $0$ and $n^d$.

We have $\Gamma$ accept iff either $v = 0$, or $\psi_v(y_v) = 1$.

Now let $M^*(\Gamma)$ denote the maximum value $v$, such that the restricted circuit $\Gamma(v, \cdot, \ldots, \cdot)$ is satisfiable. (This quantity is always at least 0).

Suppose we can efficiently produce a list $S$ of possible values for $M^*(\Gamma)$. Then the claim is that in our list $\psi_1, \ldots, \psi_{n^d}$, we can throw away all $\psi_i$ for which $i \notin S$; the resulting list contains a satisfiable formula iff the original one did. I hope this is clear by inspection.

Conclusion: we can't reliably produce a list $S$ of $\leq n^{d'}$ possible values for $M^*(\Gamma)$, unless the poly hierarchy collapses.

Second Step: We reduce from the problem of list-computing $M^*(\Gamma)$ to that of list-computing $M(\phi)$ for 3-SAT instances $\phi$.

To do this, we first run Cook's reduction on $\Gamma$ to get a 3-SAT instance $\phi_1$ of size $m = poly(n^d)$. $\phi_1$ has the same variable-set as $\Gamma$, along with some auxiliary variables. Most important for our purposes, $\phi_1(v, \cdot)$ is satisfiable iff $\Gamma(v, \cdot)$ is satisfiable.

We call $\phi_1$ the `strong constraints'. We give each of these constraints weight $2m$ (by adding duplicate constraints).

Then we add a set of `weak constraints' $\phi_2$ which add a preference for the index $v$ (defined in step 1) to be as high as possible. There is one constraint for each bit $v_t$ of $v$, namely $[v_t = 1]$. We let the $t$-th most significant bit of $v$ have a constraint of weight $m/2^{t-1}$. Since $v$ is of length $d \log n + 1$, these weights can be made integral (we just need to pad to let $m$ be a power of 2).

Finally, let $\phi = \phi_1 \wedge \phi_2$ be the output of our reduction.

To analyze $\phi$, let $(v,z)$ be the variable-set of $\phi$, with $v$ as before. First note that given any assignment to $(v, z)$, one can infer the value of $v$ from the quantity $N(v, z) =$ (total weight of $\phi$-constraints satisfied by $v, z$).
This follows from the hierarchical design of the constraint-weights (similarly to a technique from Luca's answer). Similarly, the maximum achievable value $M(\phi)$ is achieved by a setting $(v, z)$ that satisfies all strong constraints, and where (subject to this) $v$ is as large as possible. This $v$ is the largest index for which $\Gamma(v, \cdot)$ is satisfiable, namely $M^*(\Gamma)$. (Note, it is always possible, by setting $v =$ all-0, to satisfy all strong constraints, since in that case $\Gamma(v, \cdot)$ is satisfiable.)

It follows that, if we are given a list $S$ of possible values of $M(\phi)$, we can derive a list of $|S|$ possible values of $M^*(\Gamma)$. Thus we can't have $|S| \leq n^{d'}$ unless the poly hierarchy collapses. This gives the Claim, since $n^{d'} = m^{\Omega(1)}$.

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