Conservapedia

P=NP

This is an old revision of this page, as edited by Ed Poor (talk | contribs) at 23:25, August 15, 2010. It may differ significantly from current revision.

Whether P=NP is an unsolved problem in computer science. Informally, the problem asks if all problems whose solutions can be checked quickly can have those solutions found quickly. More formally, a collection of yes or no questions is a said to be in P if there exists a Turing machine T, an integer k and constant C such that which which will correctly answer whether the answer is yes or no, and the Turing machine will always terminate after a number of steps bounded by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Cn^k} where n is the length of the input. A problem is said to be in NP if the same holds true for a non-deterministic Turing machine. It is not hard to see that any problem in P is also in NP. It is unknown if P=NP or not. This problem is one of the seven Millennium problems which each have a million dollar prize.

Links

Retrieved from "https://www.conservapedia.com/index.php?title=P%3DNP&oldid=805986"