4:31 AM
So... I'm in "Advanced Algorithms and Analysis", a masters class. It might be called intro to advanced... i don't remember. it feels like the algebra level of everything.
We covered dynamic programming and divide and conquer etc.. Now we're covering NP and spending a lot of time doing reductions.
At some point, I wonder how much value another reduction is. What is there after this? What are the next steps?
Is it studying the properties of NP and the neighboring classes, the properties of specific NP problems, approximation algorithms, etc etc?
I recently thought "well if we could solve on NP problem, we could theoretically make P practically equal NP"... unfortunately, a variety of problems arise, such as that even increasing the problem instance size by a constant factor can blow the calculation time out of the water if it's an exponential algorithm.
But to me it would seem that that is where a lot of value is... a question like that. Finding properties in certain NP problems that allow less and less to be precomputed, and more and more to be efficiently reduced to something that can be guessed with a high degree of accuracy or that can be looked up in a precomputed table.
sort of connecting the graph of NP complete problems and tagging the whole thing with properties... I wonder if that exists anywhere on the web right now...
solve one*

4 hours later…
9:03 AM
Quick poll: is (pure) category theory ontopic?
0

I am reading text books of category theory, and trying to apply it. My question comes from: Luca Cardelli, Andrew D. Gordon. Mobile Ambients. In Proceedings of POPL'98. In the paper, An ambient is a bounded placed where computation happens, it can be nested within other ambients, and it can be...

0

For monoidal category, i think that tensor product is parallel relationship for morphisms. Then, If there are $f:A\rightarrow B$, $g:B\rightarrow C$,and $f$,$g$ are in the same category. Can i set up a map from tensor product to composition something like this: $f\otimes g\rightarrow g\circ f$?? ...

Imho, these fall into the "pure mathematics without obvious relation to CS", even though I know that functional programming has ties to category theory.

@Raphael That's a CS paper, so the question is definitely on-topic. It's math applied to CS theory.
@Raphael this has no mention of CS anywhere, it's pure math.

9:37 AM
@Gilles Ah, POPL, right.
*snicker*
(Well, venue alone is not a good indicator for whether something is CS. There was plenty of pure mathematics at AofA, for instance.)

8 hours later…
5:27 PM
@rotia Gain some rep anywhere on the network, then you'll be able to post.
Note that by "reducing P to NP-complete problem Q" (as you put it), you only show that P is in NP, not that it's hard. For that you need the other direction.
Our reference questions may interest you:
1

Why have I been sent here? Complexity Theory What is the difference between an algorithm, a language and a problem? How can we assume that basic operations on numbers take constant time? In basic terms, what is the definition of P, NP, NP-Complete, and NP-Hard? Optimization version of decision...

1 hour later…
6:52 PM