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...
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...
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.
@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.
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...
@Raphael I finally made it here, in the paper there are three sections. In the first one i describe how to reduce tetris to 2-partition, and in the second one i describe how the tetris board can only be cleared if we can partition the set in two halfs with the same sum, that section is called PROOF THAT THE ABOVE PROBLEM CAN ONLY BE SOLVED IF THE SET CAN BE PARTITIONED INTO TWO SUBSETS OF EQUAL SUM
@Raphael also note that in the formulas to calculate the height of the buckets i use the floor function that is because if i have a set like 2 5 8 that cannot be partitioned into two halfs with the same sum, the result will be a decimal number not an integer, so in the case 2 5 8 it will result in 15/2 = 7,5 and that gets floored to 7 so the buckets are always of insuficient height in an unsatisfiable configuration and the board cant be cleared
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...
