### A Category of problems

Posted:

**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 Prob

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 A

Each morphism f:A->B in Prob has 2 functions associated with it. It has f

f

f

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

(g compose f)

(g compose f)

for any A in Prob , id

(halp how do I do subscripts inside subscripts?)

and (id

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, Prob

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

(A+B)

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.

Thanks,

-madaco

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 Prob

^{op}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 A

_{s}be the object in S that corresponds to A.Each morphism f:A->B in Prob has 2 functions associated with it. It has f

_{s}:A_{s}->B_{s}and f_{t}:A_{s}->N .f

_{s}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 f_{s}function part of it be n ↦ 2n . f_{s}(n)=2n.f

_{t}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}= (g_{s}compose f_{s})(g compose f)

_{t}= (g_{t}compose f_{s}) + f_{t}for any A in Prob , id

_{A}:A->A , (id_{A})_{s}= id_{A[sub]s}[/sub] : A_{s}->A_{s}.(halp how do I do subscripts inside subscripts?)

and (id

_{A})_{t}= ∗↦0 : A_{s}->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, Prob

^{op}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}= A_{s}⨯B_{s}. (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.

Thanks,

-madaco