28
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 17 '10 at 3:36
  • 1
    $\begingroup$ Not sure this helps, but I'll give it a shot: On isomorphisms and density of NP and other complete sets. See also the journal version. See also Mahaney's paper. $\endgroup$ – M.S. Dousti Nov 17 '10 at 4:14
  • 2
    $\begingroup$ 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 (cse.iitk.ac.in/users/manindra/survey/Isomorphism-Conjecture.pdf). $\endgroup$ – Ramprasad Nov 17 '10 at 6:58
  • 1
    $\begingroup$ @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! $\endgroup$ – Joshua Grochow Nov 18 '10 at 17:00
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Nov 18 '10 at 17:29
21
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.