Algorithm/Complexity for the following SAT Version

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.

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

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

• Why will there necessarily be "a poly-time $S$-solver $M$ using $n^c$ parallel NP queries followed by a witnessing query"? ​ ​ – user6973 Jun 5 '16 at 4:11
• This is the equivalent characterization of the class from the third paragraph. – Emil Jeřábek Jun 5 '16 at 10:33
• That's basically what I'm asking about. ​ Why are they equivalent? ​ ​ ​ ​ – user6973 Jun 5 '16 at 10:35
• 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. – Emil Jeřábek Jun 5 '16 at 10:38
• 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? ​ ​ ​ ​ – user6973 Jun 5 '16 at 10:54