Question (and not sure if it's worth a "real" question): Say I have a set $M \subseteq N$ and a number $k \in N$, and I want to compute the set $S = \{ s \subseteq M | \sum_{i \in s} i \leq k\}$. In other words: I want to enumerate all the subsets of M which sum up to at most k.
Obviously, that's not polynomial. However, I wonder if it can be done in O(poly(|S|)) instead of the obvious O(2^{|M|}).
Or, in other words: Is that fixed-parameter tractable in |S|?
@LukasBarth Ooh, FPT questions. My favourite! I think you should just ask this on the main site (Computer Science). Honestly, FPT is close enough to state of the art research such that most questions about it are non-trivial to most!
At the least, that would render the TeX!
@LukasBarth I mean, we get far more trivial questions here that have good answers. Sometimes, a 'trivial' question has a non-trivial answer, especially if the answer is didactically excellent
I mean, our standards (for 'difficulty of questions') are a lot lower than on TCS or MO, if that's your baseline.
@LukasBarth "open problem in science"-level is a bit too much. I mean, there are rather basic FPT questions on TCS. It's just that you may think whether your question is of a 'research' level. Rule of thumb: if it's from an undergrad course, ask here. If it's a masters' course, look around and guess. If you need a PhD to understand it well, go to TCS.
But the frontier on research moves. Questions on basic automata theory was once high level research, but is now 1st year undergrad stuff.
Here I go, on brief vacation to other places on the network and what do I see when I return? The queues are a mess! Can't you people manage the queues with the 1 and a half reviewer when I'm not available? Not that I don't appreciate it, mind. It just pains me how much clearing queues apparently depends on me.
