-1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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. ♦
    Jul 7 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
    Jul 7 at 19:18

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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