Schaefer's dichotomy theorem ensures than when a constraint satisfiability problem satisfies certain conditions, the problem is either in $\mathsf P$ or is $\mathsf{NP}$-hard.

Suppose the following problem:

Given a monotone CNF $f(X)$ and a 2-CNF $g(X)$ such that $|g(X)|\le \log_c^k |f(x)|$ (where $|f|$ stands for the amount of machine words used to encode $f$) decide if $f(X)\land g(X)$ is satisfiable.

$c>1$ and $k$ are fixed (i.e. are not a part of the input). This problem is in $\mathsf{QP}$, but does Schaefer's dichotomy still apply to it or does the way the problem is formulated not satisfy the conditions in which the theorem applies?

  • $\begingroup$ Have you tried reading the statement of Shaefer's theorem and seeing whether it applies? It seems like a straightforward matter to check each condition of Shaefer's theorem. If all of the conditions are satisfied, the theorem applies; if they are not, it doesn't. What have you tried, and where are you stuck? $\endgroup$
    – D.W.
    Commented Jul 7, 2023 at 19:09
  • $\begingroup$ An unrestricted variant of this problem, where both parts can be linear in the size of the input, is $NP$-complete. This restricted variant is in $QP$, and $NP\subset QP$ is considered unlikely. However, I don't see a straightforward way to reduce this problem to a polynomially large instance of either Horn-renamable CNF, 2-CNF or affine formulae. The part I am asking about is whether the $\log_c^k$ part not violate the "A finite set of relations S over the Boolean domain" condition. $\endgroup$
    – rus9384
    Commented Jul 7, 2023 at 19:18

1 Answer 1


Schaefer's theorem is stated in many places, e.g., on Wikipedia. Can you define a set $S$ of relations so that your problem has the form specified in Schaefer's theorem? No, you cannot. Therefore, Schaefer's theorem does not apply. You will have to seek other tools to understand its complexity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.