A Category of problems

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Posts: 165
Joined: Sat Feb 13, 2010 11:25 pm UTC

A Category of problems

Postby madaco » Wed Mar 15, 2017 12:54 am UTC

I'm not sure if this goes here or in the fleeting thoughts section, or maybe even in the math subforum, but this is my best guess.

As always, I expect that this is either not useful, or is already known about, or a more useful version is already known, but I don't know where to find it.

I'm not sure how to search for this sort of thing. Of course, if this category is already thought about as a category I assume the names I am using are not the standard names to use, so sorry for that. Again, I don't know how to look this sort of thing up.

Here is a way of viewing different computational problems as being objects of a category.

Have there be 2 categories, Prob (the main one), and S (the category where the objects are the spaces for the sizes of different cs problems).

If Prob is already an accepted name of some other category (like, something about probability maybe?) then oops. I was calling it C but then I wanted to call an object C, so I picked a name.

I'm not sure which of Prob or Probop is the more natural one so I will just say the one I thought of first. (If the other one is more natural, I assume the one which is more natural would be the one that would be given the name without op in it )

The morphisms between objects correspond to reductions of one problem to another.
Each object in Prob has a object it corresponds to in S, representing the space of sizes of problems for that type of problem. (So, as an example, for the object "sorting a randomly ordered list" in Prob, the object in S would be "the collection of possible sizes of a list which is to be sorted", so, the set of natural numbers.) Different objects in Prob are allowed to correspond to the same object in S.

Where A is an object of Prob, let As be the object in S that corresponds to A.

Each morphism f:A->B in Prob has 2 functions associated with it. It has fs:As->Bs and ft:As->N .

fs represents how the problem size after the reduction (in B) depends on the problem size before the reduction (in A). So if a reduction reduces problems in A with size n to problems in B with size 2n, the morphism f for that reduction would have the fs function part of it be n ↦ 2n . fs(n)=2n.

ft represents how much time the reduction takes, depending on the size of the problem being reduced.

if f:A->B and g:B->C in Prob , then the composition of f has these functions:

(g compose f)s = (gs compose fs)

(g compose f)t = (gt compose fs) + ft

for any A in Prob , idA:A->A , (idA)s = idA[sub]s[/sub] : As->As .

(halp how do I do subscripts inside subscripts?)

and (idA)t = ∗↦0 : As->N (by which I mean, the function that takes any input in the domain, and return 0.)

It can be seen that this is indeed an identity morphism, as composing it with a thing yields that other thing.

Composition of these morphisms yields a morphism that works like this, composition is associative, all objects have an identity morphism, this is a category.


Now with that explained, a few things I've looked at in this category.

A question that I thought to ask was "what about the object/problem which corresponds to "solve these other two problems".

My first expectation was that this would be the product object of the two objects, but it turns out it is the coproduct. This is because either of the two problems can be reduced to it, but it isn't true that it can be reduced to either problem. This is one reason why I wonder why the opposite category, Probop might be more natural. Anyway, in Prob, the product of two objects A, B, seems to be the problem of "solve either this problem from A, or this problem B, of your choice.".

let A+B refer to the coproduct of A and B.

(A+B)s = As⨯Bs . (another reason I wonder if the opposite category might be more natural.)

It seems to make sense to have an object which represents the empty problem, where nothing is needed to be done to solve it. There would be a morphism from it to any object, because for any solution of a problem, you can solve the empty problem by first, solving that other problem, and then discarding the result. So it is kind of like the initial object, except the morphisms aren't unique. I don't know what to call something like that.

A problem with no solution (not merely one that can't be computed, but which has no solution) would I guess be the terminal object, because if (vacuously) you were given a solution to it, you could solve any problem, so any problem can be reduced to it.

I'm not sure what the co-exponential object of two objects would be?


So yeah.

Is this an interesting/coherent way of looking at things?

Any feedback would be appreciated.


I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.

Posts: 165
Joined: Sat Feb 13, 2010 11:25 pm UTC

Re: A Category of problems

Postby madaco » Sun Mar 19, 2017 5:11 am UTC

Alright, so apparently ~217 people have viewed this, but none have decided to respond.

I am not sure if this is because what I said was uninteresting, or because it was unclear. I don't know which one to hope for.


A reduction of a problem to the empty problem would be a solution to the problem.

If you take the subcategory which only includes the reductions where the time function and the size function for the reduction are both polynomial, then the problems (objects) which have an arrow/reduction to the empty problem are exactly the problems which are in P. (this continues to be a category because composition of polynomials are polynomials, and sums of polynomials are polynomials, so if a pair of morphisms are in the subcategory, then so is their composition. Also, the identity morphisms are still in the category. So it is indeed a subcategory.)

In this subcategory, things in NP are those that have an arrow to, say, 3SAT. (or any of the other NP-complete problems).

If you keep the whole category, the problems which have an arrow to the empty problem are exactly the computable problems.

Similarly, only allowing reductions with linear time and space functions still gives a category.

Generally, If the class of functions allowed for the size functions for the morphisms is closed under composition (when defined), and the class of functions allowed for the time functions is closed under addition (when defined) and composition with the functions for the time functions (when defined), then it is still a category. (by "when defined", I mean when the domains and codomains fit)


This seems to me like it could be a nice way to formulate certain statements/questions. Of course, these things already have other nice ways to say them, but this seems like it could also be a nice way to talk about them?

Any feedback, whether it is "I don't know what you are talking about" to "that's dumb" to "you don't realize it but you are actually talking nonsense" to "everyone already knows that", to whatever is welcome.
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.

Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests