Metraipolis › archive › dc_e548fd5ebaeb

Deskriptive Komplexitätstheorie — Wikipedia (de)

Source: Wikipedia (de)
Original: https://de.wikipedia.org/wiki/Deskriptive_Komplexit%C3%A4tstheorie
License (as archived): CC-BY-SA-4.0
Archived: 2026-11-05T05:38:50.547Z
SHA-256 of the archived text: ae76b0b8090a88a1b6f3234c8816a1a5de70e58953b4a51efd2d1f422b926aa1
Stable URL of this page: https://metraipolis.com/documento/dc_e548fd5ebaeb

How to cite

Deskriptive Komplexitätstheorie — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Deskriptive_Komplexit%C3%A4tstheorie (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_e548fd5ebaeb (Metraipolis archive dc_e548fd5ebaeb, sha256 ae76b0b8090a88a1b6f3234c8816a1a5de70e58953b4a51efd2d1f422b926aa1)

BibTeX

@misc{dce548fd5ebaeb,
  title = {Deskriptive Komplexitätstheorie — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Deskriptive_Komplexit%C3%A4tstheorie},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_e548fd5ebaeb; sha256 ae76b0b8090a88a1b6f3234c8816a1a5de70e58953b4a51efd2d1f422b926aa1},
  year = {2026}
}

Archived text

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

Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) definiert werden, lassen sich mit Hilfe der deskriptiven Komplexitätstheorie diese Klassen auch durch „natürliche“ Logiken wie der Prädikatenlogik erster oder höherer Stufe oder Fixpunktlogiken charakterisieren.

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 «Deskriptive Komplexitätstheorie» — https://de.wikipedia.org/wiki/Deskriptive_Komplexit%C3%A4tstheorie
Wikidata Q1200755: «branch of mathematical logic» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1200755
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Deskriptive_Komplexit%C3%A4tstheorie?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 267327016, consultata il 2026-11-05T05:35:52.001Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f272dacfb618e047eb2be2bf74544736a958825b8d3ec6b6ee888899f5a64cc5