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:

    “Having children can smooth the relationship, too. Mother and daughter are now equals. That is hard to imagine, even harder to accept, for among other things, it means realizing that your own mother felt this way, too—unsure of herself, weak in the knees, terrified about what in the world to do with you. It means accepting that she was tired, inept, sometimes stupid; that she, too, sat in the dark at 2:00 A.M. with a child shrieking across the hall and no clue to the child’s trouble.”
    —Anna Quindlen (20th century)

    “Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan “Press On”, has solved and will always solve the problems of the human race.”
    —Calvin Coolidge (1872–1933)