Random article ( of 1049 ) Latest updates

User Tools

Site Tools


content:mathematics:p_vs_np

Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown

The 'P versus NP' problem

The 'P versus NP' problem is a major unsolved enigma in mathematical computer science,

It was first described in 1971 by mathematician Stephen Cook in his paper entitled 'The complexity of theorem-proving procedures' Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151โ€“158.

In simple terms :

There are some mathematical problems which can be 'solved' by a computer algorithm - given enough time - (e.g. finding the factors for a very large prime number). [ called P problems ]

Some problems can be 'verified' by a computer if its provided with the answer in advance to check (also, given enough time) [ called NP problems ]

Are the two scenarios equivalent? In other words, if one is true for a certain problem, is the other automatically true? Or, are there some problems where a solution can be 'verified', but not 'solved' with a computing algorithm - no matter how much time is available?

To date, the P versus NP problem itself remains unsolved.

Editor's note : It's not easy to find an explanation and description of the problem in plain language. Here is a good description from Daniel Miessler


Show another (random) article

Suggestions for corrections and ideas for articles are welcomed : Get in touch!


Further resources :

Do NOT follow this link or you will be banned from the site!

DOKUWIKI IMPLEMENTATION DESIGN BY UNIV.ORG.UK APRIL 2024