graph algorithms and we arrive at the same set of contradictions thuswe see that the program loop cannot possibly exist the class np few steps down from the horrors of undecidable problems lies the class np np stands for nondeterministic polynomial-time deterministic machineat each point in timeis executing an instruction depending on the instructionit then goes to some next instructionwhich is unique nondeterministic machine has choice of next steps it is free to choose any that it wishesand if one of these steps leads to solutionit will always choose the correct one nondeterministic machine thus has the power of extremely good (optimalguessing this probably seems like ridiculous modelsince nobody could possibly build nondeterministic computerand because it would seem to be an incredible upgrade to your standard computer (every problem might now seem trivialwe will see that nondeterminism is very useful theoretical construct furthermorenondeterminism is not as powerful as one might think for instanceundecidable problems are still undecidableeven if nondeterminism is allowed simple way to check if problem is in np is to phrase the problem as yes/no question the problem is in np ifin polynomial timewe can prove that any "yesinstance is correct we do not have to worry about "noinstancessince the program always makes the right choice thusfor the hamiltonian cycle problema "yesinstance would be any simple circuit in the graph that includes all the vertices this is in npsincegiven the pathit is simple matter to check that it is really hamiltonian cycle appropriately phrased questionssuch as "is there simple path of length ?can also easily be checked and are in np any path that satisfies this property can be checked trivially the class np includes all problems that have polynomial-time solutionssince obviously the solution provides check one would expect that since it is so much easier to check an answer than to come up with one from scratchthere would be problems in np that do not have polynomial-time solutions to date no such problem has been foundso it is entirely possiblethough not considered likely by expertsthat nondeterminism is not such an important improvement the problem is that proving exponential lower bounds is an extremely difficult task the information theory bound techniquewhich we used to show that sorting requires ( log ncomparisonsdoes not seem to be adequate for the taskbecause the decision trees are not nearly large enough notice also that not all decidable problems are in np consider the problem of determining whether graph does not have hamiltonian cycle to prove that graph has hamiltonian cycle is relatively simple matter--we just need to exhibit one nobody knows how to showin polynomial timethat graph does not have hamiltonian cycle it seems that one must enumerate all the cycles and check them one by one thus the non-hamiltonian cycle problem is not known to be in np np-complete problems among all the problems known to be in npthere is subsetknown as the np-complete problemswhich contains the hardest an np-complete problem has the property that any problem in np can be polynomially reduced to it