What are P, NP-Complete, and NP-Hard? I ended up writing this for someone on StackOverflow ; thought I’d preserve it here too. We start with the idea of a decision problem, a problem for which an algorithm can always answer “yes” or “no.” We also need the idea of two models of computer (Turing machine, really): deterministic and non-deterministic. A deterministic computer is the regular computer we always thinking of; a non-deterministic computer is one that is just like we’re used to except that is has unlimited parallelism, so that any time you come to a branch,
Read full article from What are P, NP-Complete, and NP-Hard? | Explorations
No comments:
Post a Comment