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:

    All of us realize that war requires action. What is sometimes harder for us to realize is that peace and neutrality also require action.
    Lyndon Baines Johnson (1908–1973)

    If we fail to meet our problems here, no one else in the world will do so. If we fail, the heart goes out of progressives throughout the world.
    Eleanor Roosevelt (1884–1962)