« first day (989 days earlier)   

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?
Q: Mobile Ambients and structure

rpi-fanI 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...

Q: tensor product and composition (in monoidal category)

rpi-fanFor 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.
(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:
A: Reference answers to frequently asked questions

RaphaelWhy 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
hi millie what is your undergrad degree in
4 hours later…
11:20 PM
@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
I should put that in the paper...

« first day (989 days earlier)