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)

    “What we know, is a point to what we do not know.” Open any recent journal of science, and weigh the problems suggested concerning Light, Heat, Electricity, Magnetism, Physiology, Geology, and judge whether the interest of natural science is likely to be soon exhausted.
    Ralph Waldo Emerson (1803–1882)