Metraipolis › archive › dc_75ef571d03f8
Complexité descriptive — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-05T09:44:26.685Z
- SHA-256 of the archived text
a6e1198734d548773dd2ccf5c3fa85bb7ee2eaa7945790a1f159cb917e5f57ac- Stable URL of this page
https://metraipolis.com/documento/dc_75ef571d03f8
How to cite
Complexité descriptive — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_75ef571d03f8 (Metraipolis archive dc_75ef571d03f8, sha256 a6e1198734d548773dd2ccf5c3fa85bb7ee2eaa7945790a1f159cb917e5f57ac)
BibTeX
@misc{dc75ef571d03f8,
title = {Complexité descriptive — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_75ef571d03f8; sha256 a6e1198734d548773dd2ccf5c3fa85bb7ee2eaa7945790a1f159cb917e5f57ac},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in francese, in ordine alfabetico). Fonte: Wikipedia in francese, voce «Complexité descriptive» — https://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive 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://fr.wikipedia.org/wiki/Complexit%C3%A9_descriptive?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 240728881, consultata il 2026-11-05T09:40:14.751Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2b37d42924138e5f4b069b2ea23120311b28ecfd8b5347e5d44c42af73bd0070