P Versus NP Problem - Harder Problems

Harder Problems

See also: Complexity class

Although it is unknown whether P = NP, problems outside of P are known. A number of succinct problems (problems that operate not on normal input, but on a computational description of the input) are known to be EXPTIME-complete. Because it can be shown that P EXPTIME, these problems are outside P, and so require more than polynomial time. In fact, by the time hierarchy theorem, they cannot be solved in significantly less than exponential time. Examples include finding a perfect strategy for chess (on an N×N board) and some other board games.

The problem of deciding the truth of a statement in Presburger arithmetic requires even more time. Fischer and Rabin proved in 1974 that every algorithm that decides the truth of Presburger statements has a runtime of at least for some constant c. Here, n is the length of the Presburger statement. Hence, the problem is known to need more than exponential run time. Even more difficult are the undecidable problems, such as the halting problem. They cannot be completely solved by any algorithm, in the sense that for any particular algorithm there is at least one input for which that algorithm will not produce the right answer; it will either produce the wrong answer, finish without giving a conclusive answer, or otherwise run forever without producing any answer at all.

Read more about this topic:  P Versus NP Problem

Famous quotes containing the words harder and/or problems:

    “Your child...may not call you or other people names.... Don’t be tempted to gloss over this issue. You may be able to talk to yourself into not minding being called names, but this decision may come back to haunt you in later years. If you let a preschooler speak disrespectfully to you now, you’ll have a much harder time of it when your child is a preteen and the issue resurfaces, which it is likely to do then.”
    —Lawrence Balter (20th century)

    “I believe that if we are to survive as a planet, we must teach this next generation to handle their own conflicts assertively and nonviolently. If in their early years our children learn to listen to all sides of the story, use their heads and then their mouths, and come up with a plan and share, then, when they become our leaders, and some of them will, they will have the tools to handle global problems and conflict.”
    —Barbara Coloroso (20th century)