Category of NP-hard languages

I may display my naiveté in all things categorical, here, but…

It seems that there’s an obvious category induced by the NP-hard languages, namely one where all objects are NP-hard languages and all arrows within a category between objects are polytime reductions.

Has anybody investigated NP-hardness (or any complexity class) within the context of category theory? It seems that nobody has, from a quick Google search, which leads me to believe that there is nothing of note in such an approach. But, if so, does anybody have any pointers to an overview?

Wanna give us a clue what you’re talking about? Is this math, linguistics, programming, or what?

Okay, there’s actually a Wikipedia article titled “NP-Hard”.

Never mind.

Yeah, I think this is one where it’s safe to assume that anyone who doesn’t understand the OP won’t be able to contribute in any meaningful way.

More searching, at home. Seems close, but not exactly what I’m thinking of.

I do not have a relevant answer, but I would just like to say I am proud to be a member of a general discussion board where somebody could post this kind of question in the realistic expectation of actually getting a relevant answer! :cool:

Is the Dope cool or what? :smiley:

JRB

With all due respect for JR Brown, I’ll save my pride until he actually gets a relevant answer. Or even a helpful clue. Or even another person with a similar question.

NP-hardness includes a lot of problems for NP complexity on up. So anything PSPACE, EXPTIME, etc. complete is also NP-hard. Even the Halting Problem is NP-hard. Problems that aren’t even computable can be NP-hard. So it doesn’t have any real cohesive meaning other than NP-hardness itself. (It’s sort of like being red. What else do red objects have in common?)

You allude to mutual polytime reductions within the class. Since SAT is NP-hard, anything that is NP-hard and polytime reduces to SAT is therefore NP-complete. Clearly anything that is NP-hard and also above EXPTIME cannot reduce to SAT.

Yeah, that qualifies. Okay, I’m proud too. :cool:

I was hoping either you or Indistinguishable would show up…

That’s interesting, and I didn’t realise that potentially uncomputable problems could be NP-hard (although after reviewing the definition of NP-hard, it’s kind of obvious :smack:). However, isn’t this problem sidestepped by changing the class under consideration from NP-hard to NP-complete?

ftg, you reminded me of a question that I’ve been meaning to ask for a while. Is every problem outside of NP NP-hard?

I don’t know much at all about Category Theory. There was some cool stuff about Abstract Families of Languages/Automata in the 1960s or so that proved some interesting things about morphisms about classes of languages. (Ginsberg and Greibach* were the top two back then.) That sort of thing.

Regarding NP-like classes, there’s the relativization idea pioneered by Baker, Gill and Solovay.

Are you looking for anything along those lines? (I.e., I’m stumped.)

  • One of the more interesting people I have been lucky to meet. One of the first (if not first) people to get a PhD in Computer Science.

Shouldn’t you be doing your homework yourself?

Kids, these days.

:wink:

ftg, thanks for the pointers, I’ll take a look at the links you provided. It seems somebody else has had a similar thought to me (in the comments), although the commenter is proposing something slightly different from what I’m proposing.

There will of course be some openness in answering this, since, if P = NP, all problems are NP-hard. So, since no one has proven P != NP, no one has yet proved your conjecture false.

That having been said, if NP-hard is defined using many-one reduction [a la Karp, rather than Turing reduction a la Cook], your conjecture would imply that NP = coNP (since, letting L be some coNP-complete problem, either L is in NP (and thus coNP <= NP), or L is not in NP (and thus L is NP-hard by the conjecture, leading to NP <= coNP); but if either of NP or coNP is contained in the other, the two are equal, by symmetry). So, since no one has proven NP = coNP, no one has yet proved your conjecture true, either.

Questions like this make me suspicious.

Like those NetFlix commercials where they are spoofing game show quizzes.

Like:

“A man walks into a store with a monkey on his left shoulder. What day is it?”

“If car is like apple, then blue is like…?”

Seriously. You guys are just making up words, aren’t you?

I know you’re not, but OPs like this one make me feel like that.

It needs a little bit more precision, although I’m not sure exactly how to go about adding it. Perhaps I should conjecture that in any class that strictly contains NP, any problem in that class but outside of NP is NP-hard–although it’s not really a conjecture, since I have no opinion on how likely it is to be true.

Yeah, the word “conjecture” wasn’t quite right, but I wanted an easy way to refer to it without writing it out again. Your proposition, let us say.

What are you taking as your notion of “class”? It seems to me that what you have said in your last post is just the same as your original formulation; after all, the language L is outside of NP just in case the class NP U {L} strictly contains NP.

I think, if all you want to do is avoid the cheap “Well, we can’t rule out P = NP, so maybe…” answer, the thing to do is to ask whether we can tighten our result to establish your original proposition as actually equivalent to some well-known conjecture/anti-conjecture (e.g., P = NP, coNP = NP), instead of merely sandwiching it inbetween two, so to speak.

As for the OP, I don’t know of any existing work along exactly these lines, but that doesn’t mean it’s not a potentially fruitful approach, or at least a useful conceptual organization. (In the last blog linked to, a commenter raises the objection that “you’re not going to get much more than new terms for complexity concepts”, but this correspondence of concepts across disciplines can be valuable in itself. One might just as well declare that studying arithmetic with the tools of group theory is simply a renaming of terms, but to be dismissive is to ignore the manner in which these shifts in perspective bring to sight the applicability of general results and machinery not previously immediately visible as relevant…).

[As a further slight nitpick, the commenter seems to have in mind a category where any two reductions between the same languages are considered equal (as evidenced by, for example, his description of languages in P as initial objects and NP-complete ones as terminal objects). But, the more interesting thing, I would think, is to look at a category which has not already gone through such preorder reflection. Alternatively, perhaps they simply meant “weak initial/terminal”].

Anyway, when starting off, I see no need to limit ourselves prematurely to the NP-hard languages. We might well first investigate the category whose objects are arbitrary languages and whose morphisms are arbitrary Turing reductions. (If we liked, we could investigate arbitrary problems as well, not just decision problems). This is the obvious categorification of computability theory (aka, recursion theory), with the poset reflection of this category being the Turing degrees. By then limiting ourselves to Cook or Karp reductions and/or NP-complete or NP-hard languages, we are simply extracting certain subcategories of interest. Off the top of my head, I can’t think of anything particularly intelligent to say about the relations between these, though I’m sure there are some adjunctions and so forth to be found.

But, as ftg points out, any proof one way or another regarding P vs. NP would have to get around the relativization problem, so one will have to find some property not preserved under reconstructing these categories relative to an arbitrary oracle in order to be able to conclude anything on that front. Still, regardless of whether such a fundamental insight is itself category-theoretic or comes externally, the framework can be helpful to structure and clarify the work which needs to be done (using the previous analogy, this would be the way one might invoke groups to present work in arithmetic even when one’s argument largely depends on fundamental insights from outside group theory; groups, categories, and so forth are conceptual tools of ubiquitous application, not merely to be invoked when unavoidably necessary).

If one is not necessarily interested in this category in particular but in connections between category theory and complexity theory more generally, one perhaps more straightforward thing to do is to investigate the category whose objects are “data types” and morphisms are computable functions between them, and its relation to its subcategory containing only polytime functions (whose output sizes are also polynomially bounded, to ensure closure under composition). Under the Curry-Howard isomorphism, we should expect such categories to correspond to some logic; I think the line of work including “bounded linear logic” and “light linear logic” is probably the one to investigate here.

In a different vein of connections between category theory, complexity theory, and logic, I also have several papers sitting around on “polynomial-time realizability” which I keep meaning to look into and yet have not gotten around. But Seely’s “Graded Multicategories of Polynomial-Time Realizers” hits all the right buzzwords. :slight_smile:

No mere edit window can keep me from making the tiny augmentations I would like to: