# How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?

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)

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