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

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

<p>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) <em>parallel</em> queries to an (ordinary) NP oracle, followed by a single query to a witnessing NP oracle that always has a positive answer.</p>

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

<p>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</p>

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

<p>such that if we identify $y$ with its binary representation,</p>

<p>$$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.$$</p>

<p>Now, if we take a satisfying assignment to $\phi_x$ with the maximal number of 1s among the $z_i$’s, then <em>all</em> 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:</p>

<p><strong>input:</strong> a (satisfiable) 3-CNF formula $\phi(x_1,\dots,x_n,y_1,\dots,y_m)$</p>

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

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

<p>A related $\fnwl$-complete problem is also given in the answer to <a href="https://cstheory.stackexchange.com/q/31482">Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?</a> .</p>

CC BY-SA 3.0
2016-06-05T10:33:29.253Z
This is the equivalent characterization of the class from the third paragraph.
Emil Jeřábek
CC BY-SA 3.0
2016-06-05T10:38:10.350Z
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
CC BY-SA 3.0
2016-06-05T11:18:54.903Z
In your expression, an FNP oracle is the same thing as a witnessing NP oracle, right? Then yes, this should also be equal, even though I don't recall this being explicitly stated in the literature.
Emil Jeřábek
CC BY-SA 3.0
2016-06-04T17:55:10.053Z
2016-06-04T17:55:10.053Z
2017-04-13T12:32:28.167Z
Emil Jeřábek
<p>Given   : A 3 SAT problem.</p>

<p>Known 1 : The SAT problem is satisfiable.</p>

<p>Known 2 : We have a solution that satisfies the given 3 SAT.</p>

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

CC BY-SA 3.0
2016-06-04T15:38:28.807Z
much thanks for the pointer.. will look into it..
TheoryQuest1
<cc.complexity-theory><ds.algorithms>
Algorithm/Complexity for the following SAT Version
TheoryQuest1
# Algorithm/Complexity for the following SAT Version

(Asked by: username_0 on 2016-06-03)

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.

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_0**: much thanks for the pointer.. will look into it..  

---

## 1 answers

### Answer by username_1 on 2016-06-04. Score: 4

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?](https://cstheory.stackexchange.com/q/31482) .

> **Comments:**
> **username_1**: This is the equivalent characterization of the class from the third paragraph.  
> **username_1**: 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.  
> **username_1**: In your expression, an FNP oracle is the same thing as a witnessing NP oracle, right? Then yes, this should also be equal, even though I don't recall this being explicitly stated in the literature.  

---

