WikiWAP
World's Largest Encyclopedia On Your Mobile.

WikiWAP

P versus NP problem

Diagram of complexity classes provided that '''P''' ≠ '''NP'''. The existence of problems outside both '''P''' and '''NP'''-complete in this case was established by Ladner.R. E. Ladner "On the structure of polynomial time reducibility," J.ACM, 22, pp. 151–171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].

The relationship between the [complexity class] es [P] and [NP] is an unsolved question in [theoretical computer science] and is also considered to be one of the most important open questions in [mathematics] . It is considered by many theoretical computer scientists to be the most important problem in the field. [Lance Fortnow] , [''The status of the P versus NP problem''] , Communications of the ACM 52 (2009), no. 9, pp. 78–86. The [Clay Mathematics Institute] , which is dedicated to increasing and disseminating mathematical knowledge, has offered a million dollar [prize] for solving this question.

In essence, the question P = NP ? asks: if 'yes'-answers to a ['yes'-or-'no'-question] can be verified "quickly" (in [polynomial time] ) can the answers themselves also be computed quickly?

Pages: 1 2 3 4 5
Next next result set page

HomeMOB logoHomeMOB.com
Best Mobile Sites For Your Mobile Devices.

WikiWAP

» WikiWAP Main.
Back to Top
---
Please help us, spread the word about: HomeMOB.com.