<p>This problem is not in <span class="math-container">$NP$</span> (unless <span class="math-container">$PH$</span> collapses), since it is already <span class="math-container">$P^{NP}$</span>-hard, see e.g. [1].</p>
<p>[1] K.W. Wagner. More Complicated Questions about Maxima and Minima, and some Closures of NP. Theoretical Computer Science, 51(1-2):53 –80, 1987.</p>
<p><strong>Edit:</strong> As it was pointed out in the comments, <span class="math-container">$NP$</span> is indeed formally defined as a collection of <em>decision</em> problems and not search problems. So what I should have said is that this problem is not <em>solvable by a non-deterministic <span class="math-container">$TM$</span> in polynomial time</em> (unless <span class="math-container">$PH$</span> collapses). Also, as it was pointed out by Emil in the comments, the problem as stated is indeed <span class="math-container">$FP^{NP}$</span>-complete, where <span class="math-container">$FP$</span> is the set of <em>search</em> problems solvable in polynomial time.</p>

CC BY-SA 4.0
2021-08-14T01:27:37.780Z
I don't understand this answer.  The problem cannot be in NP as stated (regardless of whether PH collapses), simply because it is not a decision problem.
Neal Young
CC BY-SA 4.0
2021-08-14T06:50:55.850Z
@NealYoung Right. The problem as stated is $\mathrm{FP^{NP}}$-complete. The decision problem testing the value of individual variables in the lexicographically maximal assignment is $\mathrm{P^{NP}}$-complete.
Emil Jeřábek
CC BY-SA 4.0
2021-08-14T12:44:21.140Z
@EmilJeřábek thank you for the clarification.
Neal Young
CC BY-SA 4.0
2021-08-13T19:16:00.300Z
2021-08-14T08:06:45.050Z
2021-08-14T08:06:45.050Z
Reijo Jaakkola
<p>Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or 0 if φ is not satisfiable, is NP-complete.
But how does the certificate look like? Because it is not enough to have assignment that satisfies Boolean formula φ. How can we check that it is the largest in polynomial time?</p>

CC BY-SA 4.0
2021-08-13T19:11:38.600Z
As stated the problem is not a decision problem, and so not in NP.  (Also, for some natural variants, co-SAT (TAUTOLOGY) can be reduced to them in poly-time, so they surely are not in NP (unless NP = co-NP).  Can you rewrite your post to make it more precise?
Neal Young
<np-hardness><complexity-classes><sat><np-complete>
Lexicographic Boolean satisfiability
user63167
# Lexicographic Boolean satisfiability

(Asked by: username_0 on 2021-08-13)

Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x\_1, . . . , x\_n ∈ {0, 1}^n that satisfies Boolean formula φ, or 0 if φ is not satisfiable, is NP-complete.
But how does the certificate look like? Because it is not enough to have assignment that satisfies Boolean formula φ. How can we check that it is the largest in polynomial time?

**Tags:** np-hardness, complexity-classes, sat, np-complete

> **Comments:**
> **username_1**: As stated the problem is not a decision problem, and so not in NP.  (Also, for some natural variants, co-SAT (TAUTOLOGY) can be reduced to them in poly-time, so they surely are not in NP (unless NP = co-NP).  Can you rewrite your post to make it more precise?  

---

## 1 answers

### Answer by username_2 on 2021-08-13. Score: 8 | Accepted answer

This problem is not in $NP$ (unless $PH$ collapses), since it is already $P^{NP}$-hard, see e.g. [1].

[1] K.W. Wagner. More Complicated Questions about Maxima and Minima, and some Closures of NP. Theoretical Computer Science, 51(1-2):53 –80, 1987.

**Edit:** As it was pointed out in the comments, $NP$ is indeed formally defined as a collection of *decision* problems and not search problems. So what I should have said is that this problem is not *solvable by a non-deterministic $TM$ in polynomial time* (unless $PH$ collapses). Also, as it was pointed out by Emil in the comments, the problem as stated is indeed $FP^{NP}$-complete, where $FP$ is the set of *search* problems solvable in polynomial time.

> **Comments:**
> **username_1**: I don't understand this answer.  The problem cannot be in NP as stated (regardless of whether PH collapses), simply because it is not a decision problem.  
> **username_3**: @NealYoung Right. The problem as stated is $\mathrm{FP^{NP}}$-complete. The decision problem testing the value of individual variables in the lexicographically maximal assignment is $\mathrm{P^{NP}}$-complete.  
> **username_1**: @EmilJeřábek thank you for the clarification.  

---

