Data · dataset · 2025
The Concept of NP-Completeness Introduces a Statistical Argument Against P=NP
Listed in Teesside University Research Data Repository
The concept of NP-completeness summarizes a multitude of problems that can be transformed into each other through polynomial reduction.
Description
Its main idea is: "if we solve one problem in polynomial time, we will solve them all." At first glance, this is promising. But upon closer analysis, it turns out that the mechanism of reduction itself requires that each NP-complete problem has an independent polynomial-time solution.
This is because the reduction represents a transition between initially necessary solutions for each separate problem, and not a means to simplify the solution by finding it in only one place. Therefore, with each new proven NP-complete problem, the necessity for a solution to exist for it is added, if such a solution is even possible. If even one does not have a solution, then none can.
Read the rest (1 more)
Thus, a statistical argument against P=NP is formed.
Links
Where it is published
- DOI doi.org/10.17632/gnrmxwhc6v.1 ↗
DOI / persistent id · from researchdata tees ac uk
Catalogue records · 1
- OAI-PMH record data.mendeley.com/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Adata… ↗
metadata API · from researchdata tees ac uk
Topics
- From keywords
- Earth & Environmental Science
Provenance · 1 source records, 6 field assertions
| Source | Key | Last seen | Raw |
|---|---|---|---|
| Teesside University Research Data Repository | oai:data.mendeley.com/gnrmxwhc6v.1 | 15 h ago | JSON v1 |
| Field | Assertion | Extractor | Evidence |
|---|---|---|---|
| access_level | source · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | |
| concepts[field].local:field:earth-environmental | mapping · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | |
| description | source · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | /metadata/dc/description |
| license | source · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | /metadata/dc/rights |
| publication_date | source · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | |
| title | source · researchdata tees ac uk | connector:researchdata_tees_ac_uk@1.0.0 | /metadata/dc/title |