Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Are All Problems NP Complete

  1. Nov 24, 2009 #1
    Ok basicaly it boils down to this... Two types of problems exist, simple problems and complicated problems. The current question is do the "hard" problems have a simple answer.

    Ok so here is my take on this question. All problems are "hard" problems in the fact that if you run into a problem that you have not seen before it will be hard to find the solution. But also all problems are also "easy" problems in the fact that when you run into a type of problem you have done before it will be easy for you to find the solution. So what am I trying to say? Well the question is basicaly if we can find a simple answer to one of the complicated questions then all complicated questions will have simple answers. I think this is true. I think what we lose site of is the fact that the simple problems we have today where not always simple and alot of work went into solving them. Also I would like to note that we have never been so good at solving problems that we did not need to show our work when solving them. This seems to suggest to me that while at the same time we are forgetting that all problems are simple in nature. We also have forgotten that all problems are complex or NP complete in other words. And the only reason we can solve any problems at all is because we did the slow work of putting the puzzle together to get to that point.

    Now it seems to me that we are possibly making a mistake in our way of solving problems. If the goal is to be able to solve problems without having to do the work required for solving them then we will at some point need to change our methods of learning how to solve them. Because after 4000 years of advancement we are basicaly right where we left off putting 1 and 1 together. If it is not possible to just get the answer without doing the work then I suppose we will have to be ok with that but if it is possible we should not waste time by not even being wrong by not even trying to figure it out.
  2. jcsd
  3. Dec 9, 2009 #2
    It looks like someone just discovered complexity theory :)

    What you said about "complex problems", that if there is an easy solution for one of them then all complicated questions will have simple answers is true. I think you're talking about the Cook–Levin theorem. If any NP complete problems are in P, then all of them are, and P = NP.
  4. Dec 28, 2009 #3
    Nonono, you got it all wrong. Two types of problems exist, computable problems and non-computable problems!

    In any case, complexity theory doesn't mean "hard" or "complex" in the way humans use the word every day. It specifically refers to "how fast" (polynomial time?) a non-deterministic turing machine can solve a decision problem.
  5. Dec 28, 2009 #4
  6. Jan 17, 2010 #5


    User Avatar
    Gold Member

    If you want to see a hard problem, look up the traveling salesmen problem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook