<p>The area you want to look at is called "implicit complexity theory". A random and incomplete fistful of names to Google for are Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, and Kazushige Terui. </p>

<p>The basic technique is to relate complexity classes to subsystems of linear logic (the so-called "light linear logics"), with the idea that the cut-elimination for the logical system should be complete for the given complexity class (such as LOGSPACE, PTIME, etc). Then via Curry-Howard you get out a programming language in which precisely the programs in the given class are expressible. As you might expect from the mention of linear logic, these all these systems then give rise to monoidal closed categories of various flavors, which leaves you with a purely algebraic and machine-independent characterization of various complexity classes. </p>

<p>One of the things that make this area interesting is that neither traditional complexity nor logical/PL methods are entirely appropriate. </p>

<p>Since the categories involved typically have closed structure, the combinatoric methods favored by complexity theorists often break down (since higher-order programs tend to resist combinatorial characterizations). A typical example of this is the failure of syntactic methods to handle contextual equivalence. Similarly, the methods of semantics also have trouble, since they are often too extensional (since traditionally semanticists have wanted to hide the internal structure of functions). The simplest example I know here is the closure of LOGSPACE under composition: this is AFAIK only possible due to dovetailing and selective recomputation, and you can't treat the problems as pure black boxes.</p>

<p>You will likely also want to have some familiarity with game semantics and Girard's Geometry of Interaction (and their precursor, Kahn-Plotkin-Berry's concrete data structures) if you get seriously into this area -- the ideas of token-passing representations of higher-order computations used in this work supply a lot of the intuitions for ICC.</p>

<p>Since I've pointed out the central role of monoidal categories in this work, you might reasonably wonder about the connections to Mulmuley's GCT. Unfortunately, I can't help you here, since I simply don't know enough. Paul-André Melliès might be a good person to ask, though.</p>

CC BY-SA 2.5
2010-11-30T18:00:14.870Z
2010-11-30T18:00:14.870Z
Neel Krishnaswami
<p>It's possible to categorify lots of things, but that doesn't necessarily mean they're interesting categories. So the answer to "does it make sense" depends on how you mean.</p>

<p>As for predicting whether it'd be interesting, assume some appropriate definition of reductions such that it forms a category, NPC. Category theoretically interesting questions would be things like asking whether NPC has various limits or colimits (e.g., products, coproducts, pullbacks, pushouts,...). So before going about the work of formalizing things, it'd be good to sit down and think about what these co/limits would mean and whether that meaning would be interesting to know about. If we assume NPC has pullbacks, then does the ability to take the pullback of two reductions mean anything special? Questions like these seem like they could be interesting if we wanted to figure out what the "atomic" NP-complete problems are, or how multiple NP-complete problems (or their reductions) could be combined; but complexity folks typically aren't interested in those sorts of questions IME.</p>

<p>Some follow on questions would be things like: does NPC have any interesting subcategories? is NPC a subcategory of any interesting larger categories? We already know a good deal about how NP-complete problems relate to other classes of problems, so the presumptive answer to these questions is "of course". But to put a finer point on it, what does considering these relationships from a category theoretic perspective offer that other perspectives do not? One thing that CT may offer is the question of whether there are any non-trivial adjunctions between NPC and another category. Of course, adjunctions are mainly interesting when the categories behind them are themselves interesting, so if NPC doesn't have a lot of special structure then knowing about NPC-adjunctions won't really offer much.</p>

<p>As for particular references, I don't know of any off hand but the links in the comments by Sadeq, Ramprasad, Kaveh should provide somewhere to start.</p>

CC BY-SA 2.5
2010-11-28T05:59:53.057Z
2010-11-28T05:59:53.057Z
wren romano
<p>Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, where can I find it?</p>

CC BY-SA 2.5
2011-03-07T03:34:14.873Z
By the way, a very similar question was posed on the Complexity Blog in a guest post by Jens Zumbraegel in 2008: http://blog.computationalcomplexity.org/2008/08/theory-of-reductions.html (though there weren't a whole lot of answers there either).
Joshua Grochow
CC BY-SA 2.5
2010-11-17T03:36:26.243Z
I am not sure why you want the category of only NP-complete problems, but the category of all decision problems with some fixed notion of reductions (such as polynomial-time many-one reductions) as morphisms sounds a reasonable object to consider.  I do not know the category theory at all and I cannot guess whether it is interesting or not, though.
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T04:14:24.603Z
Not sure this helps, but I'll give it a shot: [On isomorphisms and density of NP and other complete sets](http://portal.acm.org/citation.cfm?id=803628). See also the [journal version](http://link.aip.org/link/?SMJCAT/6/305/1). See also [Mahaney's paper](http://dx.doi.org/10.1016/0022-0000\(82\)90002-2).
Sadeq Dousti
CC BY-SA 2.5
2010-11-17T06:58:47.490Z
Just wanted to elaborate on Sadeq's comment. Isomorphism between $NP$-complete problems has been studied and a great deal of work has been done towards proving/disproving the Berman-Hartmanis conjecture (that states that all $NP$-complete problem are "isomorphic" under polynomial time many-one reductions). Here is a survey by Manindra Agrawal on the isomorphism conjecture (http://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf).
Ramprasad
CC BY-SA 2.5
2010-11-17T19:08:53.717Z
Awesome, I will have to check that out.
Paul Allen Grubbs
CC BY-SA 2.5
2010-11-18T16:57:47.123Z
@Sadeq, @Ramprasad: Why not re-post as answers?
Joshua Grochow
CC BY-SA 2.5
2010-11-18T17:00:33.267Z
@Tsuyoshi: even the category of NPC problems with Karp reductions could potentially be interesting -- if we really understood even that category, we'd have a much better understanding of complexity in general (since it would probably entail a much better understanding of Karp reductions, hence of polynomial time). OTOH, I'm not sure that viewing it as a category will provide a way forward to aid understanding.  I have thought about this issue some in the past, and looked for references that view complexity in this way, and not found any. I hope someone does!
Joshua Grochow
CC BY-SA 2.5
2010-11-18T17:29:08.667Z
I second Joshua. What is important is not being able to define a category, what is important is to find interesting categorical structure in it. There are interesting structures in the computability case, but for complexity I don't know. Andrej should know better and will hopefully check this question.
Kaveh
CC BY-SA 2.5
2010-11-18T22:17:23.503Z
@Joshua: My comment is too short to suit an answer. I suggest Ramprasad explains his comment in an answer.
Sadeq Dousti
CC BY-SA 2.5
2010-11-19T14:34:31.873Z
@Kaveh: What are the interesting structures in the computability case?  As I said, I've looked for papers using these ideas and not found any; I'd find any references you can provide very exciting.
Joshua Grochow
CC BY-SA 2.5
2010-11-19T18:09:52.723Z
@Joshua: I don't know much, as I said Andrej is the person to ask (this seems to be a nice question in itself that I am also interested, would you like to post it?). $\lambda$-calculus and type-theories are closely related to category theory and there has been lots of work on categorical models of them. (perhaps also effective topos, realizability topos, ... ) So functional programming seems to be the way to get into category theory. On the other hand it is hard to get the complexity classes out of $\lambda$-calculus. (I may post it as another question. :)
Kaveh
CC BY-SA 2.5
2010-11-19T18:22:00.843Z
@Joshua: See these: [1](http://reports-archive.adm.cs.cmu.edu/anon/1999/CMU-CS-99-173.ps) [2](http://pages.cpsc.ucalgary.ca/~robin/talks/estonia-winter-2010/estonia-notes.pdf) but theory B experts will know better so I suggest you post it as a new question so we can learn more.
Kaveh
<cc.complexity-theory><np-hardness><ct.category-theory>
A category of NP-complete problems?
Paul Allen Grubbs
# A category of NP-complete problems?

(Asked by: username_0 on 2010-11-17)

Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, where can I find it?

**Tags:** cc.complexity-theory, np-hardness, ct.category-theory
> **Comments:**
> **username_2**: I am not sure why you want the category of only NP-complete problems, but the category of all decision problems with some fixed notion of reductions (such as polynomial-time many-one reductions) as morphisms sounds a reasonable object to consider.  I do not know the category theory at all and I cannot guess whether it is interesting or not, though.  
> **username_3**: Not sure this helps, but I'll give it a shot: [On isomorphisms and density of NP and other complete sets](http://portal.acm.org/citation.cfm?id=803628). See also the [journal version](http://link.aip.org/link/?SMJCAT/6/305/1). See also [Mahaney's paper](http://dx.doi.org/10.1016/0022-0000\(82\)90002-2).  
> **username_4**: Just wanted to elaborate on Sadeq's comment. Isomorphism between $NP$-complete problems has been studied and a great deal of work has been done towards proving/disproving the Berman-Hartmanis conjecture (that states that all $NP$-complete problem are "isomorphic" under polynomial time many-one reductions). Here is a survey by Manindra Agrawal on the isomorphism conjecture (http://www.cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf).  
> **username_0**: Awesome, I will have to check that out.  
> **username_1**: @Sadeq, @Ramprasad: Why not re-post as answers?  
> **username_1**: @Tsuyoshi: even the category of NPC problems with Karp reductions could potentially be interesting -- if we really understood even that category, we'd have a much better understanding of complexity in general (since it would probably entail a much better understanding of Karp reductions, hence of polynomial time). OTOH, I'm not sure that viewing it as a category will provide a way forward to aid understanding.  I have thought about this issue some in the past, and looked for references that view complexity in this way, and not found any. I hope someone does!  
> **username_5**: I second Joshua. What is important is not being able to define a category, what is important is to find interesting categorical structure in it. There are interesting structures in the computability case, but for complexity I don't know. Andrej should know better and will hopefully check this question.  
> **username_3**: @Joshua: My comment is too short to suit an answer. I suggest Ramprasad explains his comment in an answer.  
> **username_1**: @Kaveh: What are the interesting structures in the computability case?  As I said, I've looked for papers using these ideas and not found any; I'd find any references you can provide very exciting.  
> **username_5**: @Joshua: I don't know much, as I said Andrej is the person to ask (this seems to be a nice question in itself that I am also interested, would you like to post it?). $\lambda$-calculus and type-theories are closely related to category theory and there has been lots of work on categorical models of them. (perhaps also effective topos, realizability topos, ... ) So functional programming seems to be the way to get into category theory. On the other hand it is hard to get the complexity classes out of $\lambda$-calculus. (I may post it as another question. :)  
> **username_5**: @Joshua: See these: [1](http://reports-archive.adm.cs.cmu.edu/anon/1999/CMU-CS-99-173.ps) [2](http://pages.cpsc.ucalgary.ca/~robin/talks/estonia-winter-2010/estonia-notes.pdf) but theory B experts will know better so I suggest you post it as a new question so we can learn more.  
> **username_1**: By the way, a very similar question was posed on the Complexity Blog in a guest post by Jens Zumbraegel in 2008: http://blog.computationalcomplexity.org/2008/08/theory-of-reductions.html (though there weren't a whole lot of answers there either).  

---

## 2 answers

### Answer by username_6 on 2010-11-30. Score: 21

The area you want to look at is called "implicit complexity theory". A random and incomplete fistful of names to Google for are Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, and Kazushige Terui.

The basic technique is to relate complexity classes to subsystems of linear logic (the so-called "light linear logics"), with the idea that the cut-elimination for the logical system should be complete for the given complexity class (such as LOGSPACE, PTIME, etc). Then via Curry-Howard you get out a programming language in which precisely the programs in the given class are expressible. As you might expect from the mention of linear logic, these all these systems then give rise to monoidal closed categories of various flavors, which leaves you with a purely algebraic and machine-independent characterization of various complexity classes.

One of the things that make this area interesting is that neither traditional complexity nor logical/PL methods are entirely appropriate.

Since the categories involved typically have closed structure, the combinatoric methods favored by complexity theorists often break down (since higher-order programs tend to resist combinatorial characterizations). A typical example of this is the failure of syntactic methods to handle contextual equivalence. Similarly, the methods of semantics also have trouble, since they are often too extensional (since traditionally semanticists have wanted to hide the internal structure of functions). The simplest example I know here is the closure of LOGSPACE under composition: this is AFAIK only possible due to dovetailing and selective recomputation, and you can't treat the problems as pure black boxes.

You will likely also want to have some familiarity with game semantics and Girard's Geometry of Interaction (and their precursor, Kahn-Plotkin-Berry's concrete data structures) if you get seriously into this area -- the ideas of token-passing representations of higher-order computations used in this work supply a lot of the intuitions for ICC.

Since I've pointed out the central role of monoidal categories in this work, you might reasonably wonder about the connections to Mulmuley's GCT. Unfortunately, I can't help you here, since I simply don't know enough. Paul-André Melliès might be a good person to ask, though.


---

### Answer by username_7 on 2010-11-28. Score: 16

It's possible to categorify lots of things, but that doesn't necessarily mean they're interesting categories. So the answer to "does it make sense" depends on how you mean.

As for predicting whether it'd be interesting, assume some appropriate definition of reductions such that it forms a category, NPC. Category theoretically interesting questions would be things like asking whether NPC has various limits or colimits (e.g., products, coproducts, pullbacks, pushouts,...). So before going about the work of formalizing things, it'd be good to sit down and think about what these co/limits would mean and whether that meaning would be interesting to know about. If we assume NPC has pullbacks, then does the ability to take the pullback of two reductions mean anything special? Questions like these seem like they could be interesting if we wanted to figure out what the "atomic" NP-complete problems are, or how multiple NP-complete problems (or their reductions) could be combined; but complexity folks typically aren't interested in those sorts of questions IME.

Some follow on questions would be things like: does NPC have any interesting subcategories? is NPC a subcategory of any interesting larger categories? We already know a good deal about how NP-complete problems relate to other classes of problems, so the presumptive answer to these questions is "of course". But to put a finer point on it, what does considering these relationships from a category theoretic perspective offer that other perspectives do not? One thing that CT may offer is the question of whether there are any non-trivial adjunctions between NPC and another category. Of course, adjunctions are mainly interesting when the categories behind them are themselves interesting, so if NPC doesn't have a lot of special structure then knowing about NPC-adjunctions won't really offer much.

As for particular references, I don't know of any off hand but the links in the comments by Sadeq, Ramprasad, Kaveh should provide somewhere to start.


---

