If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how computationally hard is it to determine if the assignment is lexicographically the first among all the satisfying assignments?

  • 2
    $\begingroup$ I suggest trying to come up with a reduction and showing us what progress you've made so far. $\endgroup$
    – D.W.
    Oct 25 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.