Recently an idea came to my mind. Suppose $V$ is vector space and $\dim V = n$. Then, since $V \simeq \mathbb{R}^n$, any conjunction of $n$ boolean formulas $\phi_1, \ldots, \phi_n$ about vectors from $V$ is basically a system of $n$ linear equations which can be solved in $O(n^3)$ time. So, for any finite-dimensional space $V$ any conjunction of $\dim V$ boolean formulas theoretically can be proven in $O(n^3)$ time. Though this thought couldn't be considered a proof or at least just something serious, I'm interested, does this kind of reasoning make sense? Is there some field of TCS that brings together abstract algebra and computer science?


1 Answer 1


"any conjunction of $n$ boolean formulas is basically a system of $n$ linear equations" - no it's not. The question appears to be based on a faulty premise, so there's not much more to say. No, the reasoning doesn't make sense. Linear equations are easier to solve than nonlinear equations, and boolean formulas are typically nonlinear.

  • $\begingroup$ But aren’t all formulas about elements of $V$ take form “$a_1x_1 + \ldots + a_kx_k = b$” since they could only be constructed from $+, \cdot, =$ symbols? So they are equivalent to some linear system even if these boolean formulas are not linear (and it seems they are not linear only if $b \ne 0$) because our formulas take truth values just by ordinary rules of how vector spaces work. $\endgroup$
    – aeet
    Aug 28, 2023 at 21:33
  • $\begingroup$ @aefrt, no, a boolean formula does not need to take that form. For instance, I would say that $(x_1=a_1 \lor x_1 = a_2) \land (x_2=a_3 \lor x_3 = a_4) \land \cdots$ is a boolean formula; and it is not of that form. If you have in mind some specific class of formulas, then I suggest you ask a new question where you define the class of formulas you have in mind and ask what is the complexity of solving it. It is possible CS.SE might be a more appropriate place for your question, as this site is for research-level questions. $\endgroup$
    – D.W.
    Aug 28, 2023 at 23:40

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.