in this section we will take brief look at this problem this topic is rather complexso we will only take quick and informal look at it because of thisthe discussion may be (necessarilysomewhat imprecise in places we will see that there are host of important problems that are roughly equivalent in complexity these problems form class called the np-complete problems the exact complexity of these np-complete problems has yet to be determined and remains the foremost open problem in theoretical computer science either all these problems have polynomial-time solutions or none of them do easy vs hard when classifying problemsthe first step is to examine the boundaries we have already seen that many problems can be solved in linear time we have also seen some (log nrunning timesbut these either assume some preprocessing (such as input already being read or data structure already being builtor occur on arithmetic examples for instancethe gcd algorithmwhen applied on two numbers and ntakes (log ntime since the numbers consist of log and log bitsrespectivelythe gcd algorithm is really taking time that is linear in the amount or size of input thuswhen we measure running timewe will be concerned with the running time as function of the amount of input generallywe cannot expect better than linear running time at the other end of the spectrum lie some truly hard problems these problems are so hard that they are impossible this does not mean the typical exasperated moanwhich means that it would take genius to solve the problem just as real numbers are not sufficient to express solution to one can prove that computers cannot solve every problem that happens to come along these "impossibleproblems are called undecidable problems one particular undecidable problem is the halting problem is it possible to have your +compiler have an extra feature that not only detects syntax errors but also all infinite loopsthis seems like hard problembut one might expect that if some very clever programmers spent enough time on itthey could produce this enhancement the intuitive reason that this problem is undecidable is that such program might have hard time checking itself for this reasonthese problems are sometimes called recursively undecidable if an infinite loop-checking program could be writtensurely it could be used to check itself we could then produce program called loop loop takes as input programpand runs on itself it prints out the phrase yes if loops when run on itself if terminates when run on itselfa natural thing to do would be to print out no instead of doing thatwe will have loop go into an infinite loop what happens when loop is given itself as inputeither loop haltsor it does not halt the problem is that both these possibilities lead to contradictionsin much the same way as does the phrase "this sentence is lie by our definitionloop(pgoes into an infinite loop if (pterminates suppose that when loopp(pterminates thenaccording to the loop programloop(pis obligated to go into an infinite loop thuswe must have loop(loopterminating and entering an infinite loopwhich is clearly not possible on the other handsuppose that when loopp(penters an infinite loop then loop(pmust terminate