<p>&quot;any conjunction of <span class="math-container">$n$</span> boolean formulas is basically a system of <span class="math-container">$n$</span> linear equations&quot; - 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.</p>

CC BY-SA 4.0
2023-08-28T21:33:07.980Z
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
CC BY-SA 4.0
2023-08-28T23:40:38.073Z
@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.
CC BY-SA 4.0
2023-08-28T20:06:20.460Z
2023-08-28T20:06:20.460Z
D.W.
<p>Recently an idea came to my mind. Suppose <span class="math-container">$V$</span> is vector space and <span class="math-container">$\dim V = n$</span>. Then, since <span class="math-container">$V \simeq \mathbb{R}^n$</span>, any conjunction of <span class="math-container">$n$</span> boolean formulas <span class="math-container">$\phi_1, \ldots, \phi_n$</span> about vectors from <span class="math-container">$V$</span> is basically a system of <span class="math-container">$n$</span> linear equations which can be solved in <span class="math-container">$O(n^3)$</span> time. So, for any finite-dimensional space <span class="math-container">$V$</span> any conjunction of <span class="math-container">$\dim V$</span> boolean formulas theoretically can be proven in <span class="math-container">$O(n^3)$</span> 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?</p>

CC BY-SA 4.0
2023-08-28T18:54:31.270Z
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
<time-complexity><linear-algebra>
Algebra in complexity theory
aeet
# Algebra in complexity theory

(Asked by: username_0 on 2023-08-28)

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?

**Tags:** time-complexity, linear-algebra

> **Comments:**
> **username_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.  

---

## 1 answers

### Answer by username_2 on 2023-08-28. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: @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.  

---

