# Algebra in complexity theory

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?

• Abstract algebra is regularly used in many parts of TCS (e.g. cstheory.stackexchange.com/q/16621/129 and 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. Aug 28, 2023 at 18:54

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