# Why do exact MaxSAT algorithms scale exponentially as a function of the number of clauses?

As stated in this recent paper from ijcai https://www.ijcai.org/Proceedings/2019/0166.pdf

The top -Exact- algorithms worst case complexities are stated as follows

where m is the number of clauses in the MaxSAT instance.

Why do MaxSAT algorithms (exact ones) scale exponentially as a function of m instead of n? Does this mean that these algorithms become worse than brute force ($$O(m2^n)$$) after m is a few multiples of n?

• How about taking a look at one of these algorithms and seeing how it works? Jun 17 at 6:51