<p><em>Scott Aaronson</em>, in <a href="https://www.scottaaronson.com/blog/?p=1293" rel="nofollow noreferrer">this</a> funny April Fools’ Day post, introduces a fictionalized <span class="math-container">$P \neq NP$</span> Proof and, among other things, he says that the proof make use of</p>
<blockquote>
<p><em>Higher topos theory</em> to solve the biggest problem there was.</p>
</blockquote>
<p>More and more often I hear about  <em><strong>Category Theory</strong></em> (of which the former <em>Higher Topos Theory</em> is part) . Some say it is one of the branches of pure mathematics that is undergoing the most dramatic developments in recent years (some say it will replace set theory as the foundation of mathematics), while others are still a bit skeptical.</p>
<p>I am not aware of an extensive use in Computer Science, but (it seems that) it is becoming more and more present (functional programming, type theory, data structures, etc.).
Furthermore, I do not believe that Scott Aaronson mentioned it at random as a tool used for a possible proof of <span class="math-container">$P \neq NP$</span>: the bird eye view it provides on mathematical and logical entities could be extremely important and help us to identify some common properties that we have never been able to see because we lacked the right tools.</p>
<p>My question is the following:
have there been researchers who have achieved important results in the field of computational complexity using the tools of category theory?
How do theoretical computer scientists see this theory?</p>

CC BY-SA 4.0
2019-10-22T02:14:58.107Z
https://arxiv.org/abs/1610.07737 - check this out. Introduces a categorical definition of complexity.
Abhiram Natarajan
CC BY-SA 4.0
2019-10-22T20:40:34.410Z
Related: https://cstheory.stackexchange.com/q/944/225. Short answer: no interesting theorems in complexity theory (so far) have been proven using category-theoretic tools, as far as I know. But other topics in theory have some such theorems.
Ryan Williams
CC BY-SA 4.0
2019-10-29T16:42:44.640Z
It is an extensively used mathematical tool in much of programming language theory and logic (in CS). Conferences like POPL, LICS and ICFP now even have sessions dedicated to category theory.
xrq
<ct.category-theory><p-vs-np>
Can Category Theory help us prove P != NP?
Yamar69
# Can Category Theory help us prove P != NP?

(Asked by: username_0 on 2019-10-21)

*Scott Aaronson*, in [this](https://www.scottaaronson.com/blog/?p=1293) funny April Fools’ Day post, introduces a fictionalized $P \neq NP$ Proof and, among other things, he says that the proof make use of

> *Higher topos theory* to solve the biggest problem there was.

More and more often I hear about ***Category Theory*** (of which the former *Higher Topos Theory* is part) . Some say it is one of the branches of pure mathematics that is undergoing the most dramatic developments in recent years (some say it will replace set theory as the foundation of mathematics), while others are still a bit skeptical.

I am not aware of an extensive use in Computer Science, but (it seems that) it is becoming more and more present (functional programming, type theory, data structures, etc.).
Furthermore, I do not believe that Scott Aaronson mentioned it at random as a tool used for a possible proof of $P \neq NP$: the bird eye view it provides on mathematical and logical entities could be extremely important and help us to identify some common properties that we have never been able to see because we lacked the right tools.

My question is the following:
have there been researchers who have achieved important results in the field of computational complexity using the tools of category theory?
How do theoretical computer scientists see this theory?

**Tags:** ct.category-theory, p-vs-np
> **Comments:**
> **username_1**: https://arxiv.org/abs/1610.07737 - check this out. Introduces a categorical definition of complexity.  
> **username_2**: Related: https://cstheory.stackexchange.com/q/944/225. Short answer: no interesting theorems in complexity theory (so far) have been proven using category-theoretic tools, as far as I know. But other topics in theory have some such theorems.  
> **username_3**: It is an extensively used mathematical tool in much of programming language theory and logic (in CS). Conferences like POPL, LICS and ICFP now even have sessions dedicated to category theory.  

---

## 0 answers

