<p>On the one hand, several people (incl. myself) have tried to apply homotopical / category-theoretic methods to complexity as you suggest, but I wouldn't say much has yet come of it in terms of understanding computational complexity classes. For some pointers, see e.g. <a href="https://cstheory.stackexchange.com/q/37345/129">&quot;The&quot; category of Turing machines?</a> or search &quot;category theory&quot; on this site.</p>
<p>On the other hand, as you know from the links in the OQ, there are plenty of applications of topology and related branches of math to understand complexity classes. To add some detail and context relevant to your question (even if some of these references are already linked in the other questions you pointed to):</p>
<ul>
<li><a href="https://arxiv.org/abs/1701.02302" rel="noreferrer">Greg Yang gave a homological proof</a> of the Minsky-Papert result that parity requires maximum degree polynomial threshold functions</li>
<li>In algebraic decision trees, bounds on homology (Betti numbers) give complexity lower bounds (Ben-Or, Yao, Steele-Yao, Bjorner-Lovasz, Dobkin-Lipton). These eventually led to <a href="https://doi.org/10.1137/S0097539794282930" rel="noreferrer">Mulmuley '99</a> which separates &quot;P from NC in the algebraic PRAM model without bit operations&quot;, but does so using arguments from algebraic geometry, not merely topological/homological considerations.</li>
<li>In Geometric Complexity Theory (which grew out of Mulmuley '99 ibid), one views a complexity class as a sequence of algebraic varieties. These varieties often come equipped with a group action, and one of the main proposals is to use the representation theory of those groups on those varieties to prove complexity class separations. In <a href="https://doi.org/10.1137/S009753970038715X" rel="noreferrer">Mulmuley-Sohoni &quot;GCT I&quot;</a> they suggest using the group action on (higher) cohomology, but as far as I know no one has yet really followed up on the cohomological suggestion.</li>
<li>The method of shifted partial derivatives can be understood in terms of Hilbert series (counting dimension). To really understand what is going on with these, the typical method in commutative algebra is to use free resolutions, which are related to (co)homology of varieties, but people have mostly used either just the Hilbert series (e.g. <a href="https://doi.org/10.1145/2629541" rel="noreferrer">Gupta-Kamath-Kayal-Saptharishi</a>) or free resolutions directly (e.g. <a href="https://doi.org/10.1016/j.jalgebra.2018.01.021" rel="noreferrer">Efremenko-Landsberg-Schenck-Weyman</a> and another <a href="http://dx.doi.org/10.1090/mcom/3284" rel="noreferrer">[ELSW]</a>), arguably not really &quot;homologically&quot;.</li>
</ul>
<p>Personally, I don't feel like I have enough intuition for what complexity classes look like topologically (either in a discrete setting like Herlihy-Rajsbaum or Yang, or in GCT) to venture a guess as to whether topological invariants as coarse as (co)homology have a chance to separate complexity classes.</p>

CC BY-SA 4.0
2024-11-30T21:15:19.377Z
2024-11-30T21:15:19.377Z
Joshua Grochow
<p>I took a complexity theory course last year (which I amlost failed), and spent a lot of time on reading introductory materials on measure theory and descriptive set theory. It now seems natural to me that <a href="https://doi.org/10.1007/978-1-4684-9339-9" rel="nofollow noreferrer">complexity of algorithms have a very topological nature</a>. For the final project of the course, I was fascinated about the existence of the <a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow noreferrer">polynomial hierarchy</a>; I now suspect that if we treat the equivalence of polynomial reduction (of which there are some various versions I'm aware) as a homotopy, the quotioent sequence of the hierarchy is indeed exact. Thus, can various computational foundations (for example, some different oracles) be viewd as different 'manifolds' (for the lack of a more accurate name), and the nuances of complexity classes arise from some algebraic topology upon it?</p>
<p>I have no adequate undergraduate level training on either of the subjects, so I hope to be informed if this is a viable approach, and if so, be introduced to some further references. Many thanks in advance.</p>
<hr />
<ul>
<li><a href="https://cstheory.stackexchange.com/q/2898/61343">Applications of topology to computer science</a></li>
<li><a href="https://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs">Examples of &quot;Unrelated&quot; Mathematics Playing a Fundamental Role in TCS?</a></li>
<li><a href="https://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/" rel="nofollow noreferrer">Seemingly impossible functional programs</a></li>
<li><a href="https://cstheory.stackexchange.com/q/30666/61343">Can differential equations be classed into their own complexity classes?</a></li>
<li><a href="https://en.wikipedia.org/wiki/Geometric_complexity_theory" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Geometric_complexity_theory</a></li>
</ul>


<complexity-classes><soft-question><equivalence><algebraic-topology>
Soft question: can complexity classes be viewed as homological ones?
Gravifer
# Soft question: can complexity classes be viewed as homological ones?

(Asked by: username_0 on 2024-11-29)

I took a complexity theory course last year (which I amlost failed), and spent a lot of time on reading introductory materials on measure theory and descriptive set theory. It now seems natural to me that [complexity of algorithms have a very topological nature](https://doi.org/10.1007/978-1-4684-9339-9). For the final project of the course, I was fascinated about the existence of the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy); I now suspect that if we treat the equivalence of polynomial reduction (of which there are some various versions I'm aware) as a homotopy, the quotioent sequence of the hierarchy is indeed exact. Thus, can various computational foundations (for example, some different oracles) be viewd as different 'manifolds' (for the lack of a more accurate name), and the nuances of complexity classes arise from some algebraic topology upon it?

I have no adequate undergraduate level training on either of the subjects, so I hope to be informed if this is a viable approach, and if so, be introduced to some further references. Many thanks in advance.

---

* [Applications of topology to computer science](https://cstheory.stackexchange.com/q/2898/61343)
* [Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?](https://cstheory.stackexchange.com/questions/1920/examples-of-unrelated-mathematics-playing-a-fundamental-role-in-tcs)
* [Seemingly impossible functional programs](https://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/)
* [Can differential equations be classed into their own complexity classes?](https://cstheory.stackexchange.com/q/30666/61343)
* <https://en.wikipedia.org/wiki/Geometric_complexity_theory>

**Tags:** complexity-classes, soft-question, equivalence, algebraic-topology


---

## 1 answers

### Answer by username_1 on 2024-11-30. Score: 10 | Accepted answer

On the one hand, several people (incl. myself) have tried to apply homotopical / category-theoretic methods to complexity as you suggest, but I wouldn't say much has yet come of it in terms of understanding computational complexity classes. For some pointers, see e.g. ["The" category of Turing machines?](https://cstheory.stackexchange.com/q/37345/129) or search "category theory" on this site.

On the other hand, as you know from the links in the OQ, there are plenty of applications of topology and related branches of math to understand complexity classes. To add some detail and context relevant to your question (even if some of these references are already linked in the other questions you pointed to):

* [Greg Yang gave a homological proof](https://arxiv.org/abs/1701.02302) of the Minsky-Papert result that parity requires maximum degree polynomial threshold functions
* In algebraic decision trees, bounds on homology (Betti numbers) give complexity lower bounds (Ben-Or, Yao, Steele-Yao, Bjorner-Lovasz, Dobkin-Lipton). These eventually led to [Mulmuley '99](https://doi.org/10.1137/S0097539794282930) which separates "P from NC in the algebraic PRAM model without bit operations", but does so using arguments from algebraic geometry, not merely topological/homological considerations.
* In Geometric Complexity Theory (which grew out of Mulmuley '99 ibid), one views a complexity class as a sequence of algebraic varieties. These varieties often come equipped with a group action, and one of the main proposals is to use the representation theory of those groups on those varieties to prove complexity class separations. In [Mulmuley-Sohoni "GCT I"](https://doi.org/10.1137/S009753970038715X) they suggest using the group action on (higher) cohomology, but as far as I know no one has yet really followed up on the cohomological suggestion.
* The method of shifted partial derivatives can be understood in terms of Hilbert series (counting dimension). To really understand what is going on with these, the typical method in commutative algebra is to use free resolutions, which are related to (co)homology of varieties, but people have mostly used either just the Hilbert series (e.g. [Gupta-Kamath-Kayal-Saptharishi](https://doi.org/10.1145/2629541)) or free resolutions directly (e.g. [Efremenko-Landsberg-Schenck-Weyman](https://doi.org/10.1016/j.jalgebra.2018.01.021) and another [[ELSW]](http://dx.doi.org/10.1090/mcom/3284)), arguably not really "homologically".

Personally, I don't feel like I have enough intuition for what complexity classes look like topologically (either in a discrete setting like Herlihy-Rajsbaum or Yang, or in GCT) to venture a guess as to whether topological invariants as coarse as (co)homology have a chance to separate complexity classes.


---

