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