User Tools

    To create and edit articles, please register and log-in

Main Menu : categories & index etc.

Main menu
Click categories to expand


A-Z listingplugin-autotooltip__plain plugin-autotooltip_bigA-Z listing

This is an alphabetical index of all content pages.


Other categories

Utilities

Contact
Register
Sandbox

Also see

Importance Ratings
News
Legal
Donate/Sponsor
Curator's rationale
AI Policy



Twitter feed 𝕏



Feeds + s.e.o. etc.
rss / xml feed
sitemap file
A-Z listing (archived)


Indexed under : Mathematics

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


    Please share this page to help promote Wikenigma !

Dear reader : Do you have any suggestions for the site's content?

Ideas for new topics, and suggested additions / corrections for older ones, are always welcome.

If you have skills or interests in a particular field, and have suggestions for Wikenigma, get in touch !


Or, if you'd like to become a regular contributor . . . request a login password. Registered users can edit the entire content of the site, and also create new pages.

( The 'Notes for contributors' section in the main menu has further information and guidelines etc.)

Automatic Translation

You are currently viewing an auto-translated version of Wikenigma

Please be aware that no automatic translation engines are 100% accurate, and so the auto-translated content will very probably feature errors and omissions.

Nevertheless, Wikenigma hopes that the translated content will help to attract a wider global audience.

Show another (random) article

Further resources :

DOKUWIKI IMPLEMENTATION DESIGN BY UNIV.ORG.UK DECEMBER 2023