5
$\begingroup$

Given : A 3 SAT problem.

Known 1 : The SAT problem is satisfiable.

Known 2 : We have a solution that satisfies the given 3 SAT.

Problem Statement: Maximize the solution, i.e. find a solution such that it contains the maximum number of 1's amongst all possible valid solutions to the given problem.

$\endgroup$
  • $\begingroup$ much thanks for the pointer.. will look into it.. $\endgroup$ – TheoryQuest1 Jun 4 '16 at 15:38
4
$\begingroup$

The search problem in the question—let me call it MAX-WEIGHT-3-SAT for now—is $\def\fnwl{\mathrm{FP^{NP[wit,log]}}}\fnwl$-complete.

Recall that $\fnwl$ is defined as the class of search problems solvable by a polynomial-time Turing machine using $O(\log n)$ queries to a witnessing NP oracle: that is, the oracle is required to provide witnesses to all its YES answers.

However, for the present purpose, the following equivalent description is more convenient: a search problem is in $\fnwl$ if it is solvable by a polynomial-time machine using (polynomially many) parallel queries to an (ordinary) NP oracle, followed by a single query to a witnessing NP oracle that always has a positive answer.

To see that MAX-WEIGHT-3-SAT is in $\fnwl$, let $\phi(x_1,\dots,x_n)$ be the input formula. First, using $n+1$ parallel NP queries, check for each $0\le w\le n$ whether $\phi$ is satisfiable by an assignment with $w$ 1s. Let $w_m$ be the maximal $w$ where the answer is positive; make a final witnessing query to get a satisfying assignment with $w_m$ 1s.

In order to show $\fnwl$-completeness, let $S$ be a search problem from $\fnwl$, and fix a poly-time $S$-solver $M$ using $n^c$ parallel NP queries followed by a witnessing query. The predicate $A(x,y,z_1,\dots,z_{n^c})$ defined as “$M$ has a run with input $x$ and output $y$ if $z_i\in\{0,1\}$ is supplied as the answer to the $i$th parallel query, and moreover, whenever $z_i=1$, this answer is indeed correct” is in NP, hence by the proof of the Cook–Levin theorem, there is a poly-time computable sequence of 3-CNF formulas

$$\phi_x(y_1,\dots,y_{n^d},z_1,\dots,z_{n^c},u_1,\dots,u_{n^d})$$

such that if we identify $y$ with its binary representation,

$$A(x,y,z_1,\dots,z_{n^c})\iff\exists u_1,\dots,u_{n^d}\,\phi_x(y,\vec z,\vec u)=1.$$

Now, if we take a satisfying assignment to $\phi_x$ with the maximal number of 1s among the $z_i$’s, then all answers supplied by $\vec z$ for the computation of $M$ are correct, and we can read of the output ($y$) from the assignment. Thus, $S$ is reducible to the following generalization of MAX-WEIGHT-3-SAT:

input: a (satisfiable) 3-CNF formula $\phi(x_1,\dots,x_n,y_1,\dots,y_m)$

output: a satisfying assignment to $\phi$ with the maximal possible number of 1s among the $x_i$’s

But in fact, this problem is reducible to the original MAX-WEIGHT-3-SAT: given $\phi$ as above, consider the formula $$\phi(\vec x,\vec y)\land\bigwedge_{i=1}^n\bigwedge_{j=1}^m(x_i\leftrightarrow z_{i,j})$$ which behaves just like $\phi$, except that each $x_i$ variable split in $m+1$ variables with the same truth value (under satisfying assignments), overwhelming the count of the $y_i$ variables.

A related $\fnwl$-complete problem is also given in the answer to Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard? .

$\endgroup$
  • 1
    $\begingroup$ Why will there necessarily be "a poly-time $S$-solver $M$ using $n^c$ parallel NP queries followed by a witnessing query"? ​ ​ $\endgroup$ – user6973 Jun 5 '16 at 4:11
  • $\begingroup$ This is the equivalent characterization of the class from the third paragraph. $\endgroup$ – Emil Jeřábek Jun 5 '16 at 10:33
  • 1
    $\begingroup$ That's basically what I'm asking about. ​ Why are they equivalent? ​ ​ ​ ​ $\endgroup$ – user6973 Jun 5 '16 at 10:35
  • $\begingroup$ That's an exercise I don't wish to spoil for you. If you get lost, follow the link, and if that still doesn't help, follow the references in the linked question. $\endgroup$ – Emil Jeřábek Jun 5 '16 at 10:38
  • $\begingroup$ Okay, I believe I've worked that out now, but if I'm right then that class simplifies to FP$^{\hspace{.02 in}||}$$^{\text{FNP}}$. $\hspace{.88 in}$ Are those in fact known to be equal? ​ ​ ​ ​ $\endgroup$ – user6973 Jun 5 '16 at 10:54

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.