Problem Detail: I was watching the videos from Skiena’s Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer scientists by biologists were proved to be NP-Complete. My questions are the following ones: ( Please forgive me, if I make blunders here in asking questions. I am not from CS background.)
- Do NP-Completeness imply no algorithm exist for that particular problem?
- The professor was talking about heuristic approaches where normal approaches fails. Do there exist ‘heuristic’ approaches in computer science to solve problems? If so , Can some one give examples. (I have heard of heuristic approaches in analog circuit design in electronics. But I am not sure. Music composition is heuristic , right?)
- Is Machine learning a solution to solve some computational problems, where traditional algorithmic solutions doesn’t exist?
Asked By : dexterdev
Answered By : Tim
I haven’t seen these lectures, but here’s what I think about he questions you pose.
- No. NP-completeness is unrelated to the existence of algorithms. For example, we have plenty of problems that we can prove only have an exponential solution. We typically talk about “is there a solution” as decidability. There are problems that have no solution and we call these undecidable. The Halting Problem is a popular example.
- Absolutely. When we can’t find an efficient solution for all inputs, we find something that works for “most cases”. In some cases, we can can prove the solution generated is not worse than K times the true optimal solution. In other cases, we cannot.
- Yes. Machine learning works well for certain classes of problems, but is really hard to apply to others. It’s not a “silver bullet” or alternate solution to computational complexity.
Regards.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/26254
