0
$\begingroup$

Boolean satisfiability problem (SAT) is NP-complete by Cook–Levin theorem. (wiki)

Horn-satisfiability – given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the boolean satisfiability problem. It is also P-complete. P-complete problems lie outside NC and so cannot be effectively parallelized. (wiki)

Is there a version of the boolean satisfiability problem that has NC complexity?

$\endgroup$

1 Answer 1

2
$\begingroup$

Allender, Bauland, Immerman, Schnoor and Vollmer showed in their paper The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem that every Boolean constraint satisfaction problem with a finite number of allowed constraints is either in $\mathsf{coNLOGTIME}$ or it is complete for one of the following classes: $\mathsf{NP}, \mathsf{P}, \mathsf{\oplus L}, \mathsf{NL}, \mathsf{L}$ (with respect to $\mathsf{AC^0}$ reductions).

$\endgroup$
4
  • $\begingroup$ Do I understand correctly: There is procedure/rules to limit the language of the Boolean constraint satisfaction problem to make it solvable in a time complexity from the listed classes. Then if I can reduce my original problem to SAT (𝖼𝗈𝖭𝖫𝖮𝖦𝖳𝖨𝖬𝖤 class) then I can expect to get a solution in $O(n\log n)$ time? $\endgroup$
    – Oleg Dats
    Apr 1, 2022 at 13:16
  • 1
    $\begingroup$ SAT doesn't belong to coNLOGTIME. coNLOGTIME has nothing to do with $O(n\log n)$ time. I suggest taking a look at the paper, consulting texts on complexity theory as needed. $\endgroup$ Apr 1, 2022 at 13:22
  • $\begingroup$ I will read the paper even if it looks complicated to me. My original question was about limiting SAT to find a variable assignment that satisfies the formula in a time complexity strictly less than P. For example NC or 𝑂(𝑛log𝑛). Can you please suggest if such a class exists? $\endgroup$
    – Oleg Dats
    Apr 1, 2022 at 14:54
  • 1
    $\begingroup$ Yes, for example if you don't allow negative literals. $\endgroup$ Apr 1, 2022 at 17:23

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.