<sod>  
 The '''P''' = '''NP''' question has also been addressed using [[Oracle machine|oracles]].
 
Although we don't know whether '''P'''='''NP''', we do know of problems outside '''P'''.  For example, the problem of deciding the truth of a statement in  [[Presburger arithmetic]] is not solvable in polynomial time, so it is outside of '''P'''.  It isn't even solvable in exponential time, so it is outside of '''NP'''.  Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has a runtime of at least 2^(2^(''cn'')) for some constant ''c''. Here, ''n'' is the length of the Presburger statement. Hence, the problem is one of the few that provably need more than polynomial run time.  Another example of a problem outside both '''P''' and '''NP''' is any undecidable problem, such as the [[halting problem]].
 
 All of the above discussion has assumed that '''P''' means "easy" and "not in '''P'''" means "hard".  While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
 *It ignores constant factors.  A problem that takes time 10<sup>1000</sup>''n'' is '''P''' (in fact, it's linear time), but is completely intractable in practice.  A problem that takes time 10<sup>-10000</sup>2<sup>''n''</sup> is not '''P''' (in fact, it's exponential time), but is very tractable for values of ''n'' up into the thousands.
 '''See also:'''
 * A $1,000,000 offer from the Clay Mathematics Institute for a solution of the '''P''' versus '''NP''' question: http://www.claymath.org/prizeproblems/index.htm 
 
 
[[talk:Complexity_classes_P_and_NP|Talk]]
 
 <eod> <sod> 
 The '''P''' = '''NP''' question has also been addressed using [[Oracle machine|oracles]].
 
Although we don't know whether '''P'''='''NP''', we do know of problems outside '''P'''.  The problem of finding the best move in [[Chess]] or [[Go]] (on an ''n''x''n'' board) is [[EXPTIME-Complete]].  This means it requires exponential time, and so is outside '''P'''.  The problem of deciding the truth of a statement in  [[Presburger arithmetic]] is also not solvable in polynomial time, so it is outside of '''P'''.  It isn't even solvable in exponential time, so it is outside of '''NP'''.  Fischer and Rabin proved in 1974 that every algorithm which decides the truth of Presburger statements has a runtime of at least 2^(2^(''cn'')) for some constant ''c''. Here, ''n'' is the length of the Presburger statement. Hence, the problem provably needs more than polynomial run time.  Another example of a problem outside both '''P''' and '''NP''' is any undecidable problem, such as the [[halting problem]].
 
 All of the above discussion has assumed that '''P''' means "easy" and "not in '''P'''" means "hard".  While this is a common and reasonably accurate assumption in complexity theory, it is not always true in practice, for several reasons:
 *It ignores constant factors.  A problem that takes time 10<sup>1000</sup>''n'' is '''P''' (in fact, it's linear time), but is completely intractable in practice.  A problem that takes time 10<sup>-10000</sup>2<sup>''n''</sup> is not '''P''' (in fact, it's exponential time), but is very tractable for values of ''n'' up into the thousands.
 '''See also:'''
 * A $1,000,000 offer from the Clay Mathematics Institute for a solution of the '''P''' versus '''NP''' question: http://www.claymath.org/prizeproblems/index.htm 
* A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. ''Automata, Languages, and Programming'', Springer LNCS 115 (1981) 278-293 and ''J. Comb. Th. A'' 31 (1981) 199-214.
* E. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
 
 
 
 <eod>