Источник / закреплённая редакция
The P versus NP Problem
Источник пакета cmi.p_vs_np · claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
- work
- urn:org:cmi:p-vs-np#CMI_PVSNP_OFFICIAL_DESCRIPTION
- номер
- claymath.org/wp-content/uploads/2022/06/pvsnp.pdf
- вид
- urn:org:cmi:p-vs-np#treatise
CMI_PVSNP_EDITION
- edition
- urn:org:cmi:p-vs-np#CMI_PVSNP_EDITION
- язык
- en
- официальность
- official
- материализация
- PINNED_UNOFFICIAL_COPY
- жизненный цикл
- —
Публикации
| URI | Тип | documentHash | Получено |
|---|---|---|---|
| https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf | text/plain; charset=utf-8 | sha256:971c57f84058eb4b06c972613055364c0c68165ba45b4a840a27e5793d777fe6 | 2026-09-17T00:00:00Z |
Фрагменты — 8
2.history · defn · на него ссылаются: 3
en · official · sha256:e47e6c53eb427423ac6799ceb20046dd55bc7d7fc87e0c5008ec8a7c32649101EN
Returning to the historical treatment of complexity theory, in 1971 the present author [9] introduced a notion of NP-completeness as a polynomial-time analog of c.e.-completeness, except that the reduction used was a polynomial-time analog of Turing reducibility rather than many-one reducibility. The main results in [9] are that several natural problems, including Satisfiability and 3-SAT (defined below) and subgraph isomorphism are NP-complete. A year later Karp [21] used these completeness results to show that 20 other natural problems are NP-complete, thus forcefully demonstrating the importance of the subject. Karp also introduced the now standard notation P and NP and redefined NP-completeness using the polynomial-time analog of many-one reducibility, a definition that has become standard.Ссылаются нормы: names-cook-1971, names-karp-1972, names_historical_result
1.def4 · defn · на него ссылаются: 1
en · official · sha256:d89693fcd136e9407707053d91ee30e0f002809a606ea0fcc6291762d3458fc4EN
Definition 4. A language L is NP-complete iff L is in NP, and L' ≤p L for every language L' in NP.Ссылаются нормы: defines-np-complete
1.NP-def · defn · на него ссылаются: 1
en · official · sha256:9955b8a1a6e7974569425679ac4721e113f43fc1fe451334f552e26d4bb50585EN
Now we define the class NP of languages by the condition that a language L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such that for all w ∈ Σ*, w ∈ L ⇔ ∃y(|y| ≤ |w|^k and R(w, y)), where |w| and |y| denote the lengths of w and y, respectively.Ссылаются нормы: defines-np
1.statement · defn · на него ссылаются: 3
en · official · sha256:a9c7c12260b500d5243b5f16798a3b32dec23012eb3b0d80c8e301ff8f3e7669EN
Problem Statement. Does P = NP?Ссылаются нормы: PvsNpFormalStatement, formal-identifies-pvsnp, source-asserts-formal
1.informal · defn · на него ссылаются: 3
en · official · sha256:01923c11adae5f13fff24049f987b972a83f0a1408947bcbf8def7dcb54d028dEN
The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time.Ссылаются нормы: PvsNpInformalStatement, informal-identifies-pvsnp, source-asserts-informal
1.P-def · defn · на него ссылаются: 1
en · official · sha256:3aa27131717e9d6220c7f274e922107308ac0db4e70174b07e60e1cbf9c489ddEN
P = {L | L = L(M) for some Turing machine M that runs in polynomial time}.Ссылаются нормы: defines-p
1.def3 · defn · на него ссылаются: 1
en · official · sha256:329fae74539a627b99e2b4ae23d366c78d5dc919514837c714b5ce7256ed5c16EN
Definition 3. Suppose that Li is a language over Σi, i = 1, 2. Then L1 ≤p L2 (L1 is p-reducible to L2) iff there is a polynomial-time computable function f : Σ1* → Σ2* such that x ∈ L1 ⇔ f(x) ∈ L2, for all x ∈ Σ1*.Ссылаются нормы: defines-p-reducible
title · defn · на него ссылаются: 4
en · official · sha256:311567f9ddbba49713c4080e7b18c545bb7c2ac27abf9e1f4a6c7cc2fe0ab31eEN
THE P VERSUS NP PROBLEM
STEPHEN COOKСсылаются нормы: CmiPvsNpSource, classified_as_millennium_problem, defines_notion, formal-classified
Хэш рядом с текстом — sha256 его точных байтов. Он и есть проверка того, что показанный текст совпадает с закреплённым в пакете: расхождение роняет статику оракула.