Metraipolis › archive › dc_623e110645fd

P versus NP problem — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/P_versus_NP_problem
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T11:27:23.855Z
SHA-256 of the archived text: f4f2aeb2a66a11f29c34cdb3f158dd26a0965c282cf303623864d3238fe66613
Stable URL of this page: https://metraipolis.com/documento/dc_623e110645fd

How to cite

P versus NP problem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/P_versus_NP_problem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_623e110645fd (Metraipolis archive dc_623e110645fd, sha256 f4f2aeb2a66a11f29c34cdb3f158dd26a0965c282cf303623864d3238fe66613)

BibTeX

@misc{dc623e110645fd,
  title = {P versus NP problem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/P_versus_NP_problem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_623e110645fd; sha256 f4f2aeb2a66a11f29c34cdb3f158dd26a0965c282cf303623864d3238fe66613},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/P_versus_NP_problem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every decision problem for which a proposed positive answer can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that solves the task and runs in polynomial time (as opposed to, say, exponential time), meaning the task completion time is bounded above by a polynomial function on the size of the input to the algorithm. The general class of questions that some algorithm can answer in polynomial time is "P" or "class P". For some questions, there is no known way to find an answer quickly, but if provided with an answer, it can be verified quickly. The class of questions where an answer can be verified in polynomial time is "NP", standing for "nondeterministic polynomial time". An answer to the P versus NP question would determine whether problems that can be verified in polynomial time can also be solved in polynomial time. If P ≠ NP, which is widely believed, it would mean that there are problems in NP that are harder to compute than to verify: they could not be solved in polynomial time, but the answer could be verified in polynomial time. The problem has been called the most important open problem in computer science. Aside from being an important problem in computational theory, a proof either way would have profound implications for mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Mathematical optimization»).
Fonte: Wikipedia in inglese, voce «P versus NP problem» — https://en.wikipedia.org/wiki/P_versus_NP_problem
Wikidata Q746242 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q746242
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/P_versus_NP_problem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378940846, consultata il 2026-10-07T11:16:47.987Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 064a958f356c1aac37bab11dc25bc5428044ebaad286f8f8c7af68c75024ad02