<sod>  Most people think that the answer is probably "no"; some people believe the question may be undecidable from the currently accepted axioms. A [[Millennium Prize Problems|$1,000,000 prize]] has been offered for a correct solution.
 
 In essence, the '''P''' = '''NP''' question asks: if positive solutions to a YES/NO problem can be ''verified'' quickly, can the answers also be ''computed'' quickly? Here is an example to get a feeling for 
the question. The [[integer factorization]] problem is this: given two [[natural number]]s ''x'' and ''y'', with ''n'' digits each, decide whether ''x'' can be evenly divided by an integer between 1 and ''y''.  No fast algorithms are known for this problem, where "fast" means "finishing in a number of steps that is at most a fixed power of ''n''". However, positive answers can be verified quickly ''given the right information'': it is easy to check whether 69799 has any factors less than 300 if given its [[prime number|prime]] factors 69799 = 223 * 313.  That is much easier than finding the factorization of 69799 in the first place. The information needed to verify a positive answer is also called a ''certificate''. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in '''NP'''. It is not known whether the problem is in '''P'''.
 
 We will now define the two classes formally.
 
                 OUTPUT "YES" (or "NO" if that was proved) and HALT
 
 '''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.
 <eod> <sod> Most people think that the answer is probably "no"; some people believe the question may be undecidable from the currently accepted axioms. A [[Millennium Prize Problems|$1,000,000 prize]] has been offered for a correct solution.
 
 In essence, the '''P''' = '''NP''' question asks: if positive solutions to a YES/NO problem can be ''verified'' quickly, can the answers also be ''computed'' quickly? Here is an example to get a feeling for 
the question. The [[integer factorization]] problem is this: given two [[natural number]]s <var>x</var> and <var>y</var>, with <var>n</var> digits each, decide whether <var>x</var> can be evenly divided by an integer between 1 and <var>y</var>.
(Taking <var>y</var> = floor(&radic(<var>x</var>)), this decision problem is equivalent to asking whether <var>x</var> is a composite number.)
No fast algorithms are known for this problem, where "fast" means "finishing in a number of steps that is at most a fixed power of ''n''". However, positive answers can be verified quickly ''given the right information'': it is easy to check whether 69799 has any factors less than 300 if given its [[prime number|prime]] factors 69799 = 223 * 313.  That is much easier than finding the factorization of 69799 in the first place. The information needed to verify a positive answer is also called a ''certificate''. So we conclude that given the right certificates, positive answers to our problem can be verified quickly (i.e. in polynomial time) and that's why this problem is in '''NP'''. It is not known whether the problem is in '''P'''.
 
 We will now define the two classes formally.
 
                 OUTPUT "YES" (or "NO" if that was proved) and HALT
 

 '''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.
 <eod>