Metraipolis › archive › dc_bab3a3fbb775
Co-NP-Vollständigkeit — Wikipedia (de)
- Source
- Wikipedia (de)
- Original
- https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-03T21:13:09.974Z
- SHA-256 of the archived text
64514558bed9f5818fbdd1585d04ce1298b1f1779060c41bfe379c698b9ff992- Stable URL of this page
https://metraipolis.com/documento/dc_bab3a3fbb775
How to cite
Co-NP-Vollständigkeit — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bab3a3fbb775 (Metraipolis archive dc_bab3a3fbb775, sha256 64514558bed9f5818fbdd1585d04ce1298b1f1779060c41bfe379c698b9ff992)
BibTeX
@misc{dcbab3a3fbb775,
title = {Co-NP-Vollständigkeit — Wikipedia (de)},
howpublished = {Wikipedia (de)},
url = {https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bab3a3fbb775; sha256 64514558bed9f5818fbdd1585d04ce1298b1f1779060c41bfe379c698b9ff992},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Als co-NP-vollständig werden in der Komplexitätstheorie diejenigen Probleme bezeichnet, die zu den schwierigsten Problemen der Komplexitätsklasse co-NP gehören. Jedes Problem in co-NP lässt sich mit höchstens polynomiellem Aufwand auf ein co-NP-vollständiges Problem reduzieren. Gilt P ungleich co-NP, so sind alle co-NP-vollständigen Probleme nicht in deterministischer Polynomialzeit lösbar. Existiert hingegen ein effizienter Algorithmus zur Lösung eines co-NP-vollständigen Problems, so kann dieser verwendet werden, um sämtliche Probleme in co-NP effizient zu lösen. Dieses Konzept ist insbesondere im Zusammenhang mit dem P-NP-Problem sowie der NP-Vollständigkeit von Interesse. Siehe co-NP und NP-Vollständigkeit für weitere Details. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico). Fonte: Wikipedia in tedesco, voce «Co-NP-Vollständigkeit» — https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit Wikidata Q1142354: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1142354 Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Co-NP-Vollst%C3%A4ndigkeit?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 267588649, consultata il 2026-11-03T20:59:37.588Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ea4ebe7f35217f9cb313ee440b1aba50c79447b2a2089cef58336676b23e8c93