It's possible to construct SAT problems that are solvable in quasipolynomial time, but they are also solvable in polylogarithmic space. Consider, for example, the following problem:

Let a set $S$ consist of $\mathcal O(\log^k n)$ variables. Suppose a boolean formula $\varphi(S, X)$ in 3-CNF form such that $\forall c\in C\ \exists l\in c:l\in S$ where $C$ is the set of clauses of $\varphi(S, X)$. Is $\varphi(S, X)$ satisfiable?

But is it possible to have some SAT variant that is solvable in quasipolynomial time (and not in polynomial time unless there are some "big" complexity theoretic implications) and not solvable in subpolynomial space (again, unless $\mathsf P$ collapses to a "smaller" class)?

  • $\begingroup$ What is subpolynomial space? $\endgroup$
    – Jxb
    Commented Dec 12, 2023 at 1:36


Your Answer

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