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
-
1$\begingroup$ 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. $\endgroup$– Joshua GrochowCommented Aug 28, 2023 at 18:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
$\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$– aeetCommented 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.Commented Aug 28, 2023 at 23:40