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.)

  1. Do NP-Completeness imply no algorithm exist for that particular problem?
  2. 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?)
  3. Is Machine learning a solution to solve some computational problems, where traditional algorithmic solutions doesn't exist?

migrated from cstheory.stackexchange.com May 30 '14 at 21:52

This question came from our site for theoretical computer scientists and researchers in related fields.


I haven't seen these lectures, but here's what I think about he questions you pose.

  1. 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.

  2. 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.

  3. 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.


  • $\begingroup$ I appreciate your effort in answering. $\endgroup$ – dexterdev May 29 '14 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.