I wanted to raise this question based on the discussion here. An example would be "What are some real world applications for genetic algorithms?"

The decision here should be added into our FAQ.


2 Answers 2

There seems to be quite a bit of interest in answering some applied questions. (I've answered some myself.) After I commented that http://cstheory.stackexchange.com/questions/2050/approximation-algorithms-for-maxsat was off topic, Peter Shor replied:

In the '80s and '90s, at many universities, theoretical computer science was very unpopular and looked down upon by the rest of computer science because it was viewed as unconnected to practice. Eventually, Google and other successes convinced them that we were worth talking to. Let's please not close off the lines of communication from the other side now, after having worked so long to open them. That would be very bad for the field, not to mention the TCS job market.

Is there a consensus that heuristic algorithms for rigorously defined problems are on-topic, even if we can't prove anything about them? Should we distinguish methods with theoretical partial results (such as branch and bound, which is easily proven correct albeit potentially exponential) from methods with very little theory (such as genetic algorithms)?

I'm in favor of entertaining such questions, because many of us (myself included) do a fair bit of 'application consulting' in addition to theory work. As Peter says, keeping lines of communication open is very important. –  Suresh Venkat Oct 20 '10 at 21:41
Yes, I think in general, we are being too quick to close nowadays. Even questions which are not research-level might have answers that are research-level, and I think for this reason, it's worthwhile to keep such questions open. It makes me a little afraid that our strictness may be limiting interesting answers... –  arnab Oct 20 '10 at 21:45
I've also answered "applied" questions, suggesting some heuristics. If we can actually say something interesting about the problem that can't be easily answered by a web search, then why not? –  Ryan Williams Oct 21 '10 at 0:33
strongly disagree that genetic algorithms have "very little theory" or that "we cant prove anything about them" & there is vast literature that easily refutes this pov... just added some new refs to the GA question in support –  vzn Sep 3 '12 at 2:50

Here's an example of an applied question that's not off topic:

I work in area X and we are trying to model the behaviour of geegaws under severe heat stress. We've formulated it as the following problem and were wondering if there was anything known about this problem.

Here's an example that is on the border:

I work in area X and want to model geegaws under heat stress. How can I do it ?

Here's an example that is off topic:

I work in area X and we have this red and green geegaw that's behaving strangely when we heat it up to 150 F in 50% humidity. How do I explain this ?

I'd say just the first question is on topic. For the second question, you'd really need to consult an engineer, and I'm presuming most of us aren't. But I'm definitely in favor of allowing as many applied questions as is reasonable. (That is, if the question is one which has a fairly good chance of involving TCS expertise, we should allow it.) –  Peter Shor Oct 20 '10 at 18:55
yes that's true. the second question would be a lot trickier. My thought was that if there was someone in TCS who's worked on the first question, they might provide pointers for the second. –  Suresh Venkat Oct 20 '10 at 21:42
Of course, if you replaced "geegaw" with "network" and "heat stress" with "terrorist attack," we would probably come up with a pretty interesting TCS problem. It might be a lot more realistic, though, if an engineer had some input into the model. –  Peter Shor Oct 21 '10 at 11:24
@peter actually there is some remarkable new historical analysis and mathematical modelling of wars and warfare that finds a inverse power law which would be applicable to algorithmic simulations etc... it may be already reflected in some simulations... –  vzn Sep 3 '12 at 2:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .