-3

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?

aeet
  • 1
  • 1
  • 1
    Abstract algebra is regularly used in many parts of TCS (e.g. https://cstheory.stackexchange.com/q/16621/129 and https://cstheory.stackexchange.com/q/25841/129). Conjunctions of Boolean formulas are in general much more complicated than linear equations, as solving a system of Boolean formulas is NP-complete while (as you note) linear equations can be solved in polynomial time. – Joshua Grochow Aug 28 '23 at 18:54

1 Answers1

2

"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.

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • 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. – aeet Aug 28 '23 at 21:33
  • @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. – D.W. Aug 28 '23 at 23:40