Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle.

The proof in [1] makes use of binary search with a search space from weight $0$ to the sum of all weights. But I am struggling with the fact that the weights could very large. For example: Let $\{c_1, ..., c_m\}$ be a set of clauses where some clause $c_i$ has weight $w_i = 2^{2^{m}}$. Then binary search will take $log_2(2^{2^{m}}) = 2^m$ steps in the worst case, which is exponential in the input length $m$.

What am I missing?

Reference: [1] Papadimitriou - Computational Complexity (1994)

  • 1
    $\begingroup$ How many bits does it take to represent a number like $2^{2^m}$? $\endgroup$ – Tom van der Zanden Feb 11 '15 at 11:37
  • $\begingroup$ @TomvanderZanden $2^m$ - got it :-) Thank you. $\endgroup$ – John Threepwood Feb 11 '15 at 12:31
  • $\begingroup$ I didn't think it was worthwhile enough to turn in to an answer, but on second thought a question should not remain unanswered. $\endgroup$ – Tom van der Zanden Feb 18 '15 at 11:52

The input length is not $m$. To represent an integer of $2^{2^m}$, one needs $\log_2{2^{2^m}}=2^m$ bits. Hence an algorithm taking $2^m$ steps is considered linear in the input length, which is $2^m$.

A number like $2^{2^m}$ can be represented by just giving $m$, but it is usually assumed that numbers are given in binary. And the result that MAX-SAT is in $FP^{NP}$ only holds when that encoding is used.


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.