About: dbpedia-fr:P_(complexité)

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: dbpedia-fr:P_(complexité) Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : fr.dbpedia.org associated with source document(s)

Attributes	Values
rdfs:label	P (complexiteitsklasse) (nl) P (complexité) (fr) Problem P (pl) Клас складності P (uk) Класс P (ru) كثير حدود (تعقيد) (ar)
rdfs:comment	La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. (fr)
rdfs:seeAlso	https://www.quora.com/topic/P-Class
sameAs	dbr:P_(complexity) wikidata:Q846354 dbpedia-ar:كثير_حدود_(تعقيد) dbpedia-ca:P_(complexitat) dbpedia-cs:P_(třída_složitosti) dbpedia-de:P_(Komplexitätsklasse) dbpedia-eo:P_(komplikeco) dbpedia-es:P_(clase_de_complejidad) dbpedia-fa:P_(پیچیدگی) dbpedia-fi:P_(vaativuusluokka) dbpedia-he:P_(מחלקת_סיבוכיות) dbpedia-it:P_(complessità) dbpedia-ja:P_(計算複雑性理論) dbpedia-ko:P_(복잡도) dbpedia-nl:P_(complexiteitsklasse) dbpedia-nn:P_i_kompleksitetsteori dbpedia-no:P_(kompleksitet) dbpedia-pl:Problem_P dbpedia-pt:P_(complexidade) dbpedia-ro:P_(teoria_complexității) dbpedia-ru:Класс_P dbpedia-sr:P_(сложеност) dbpedia-th:พี_(ความซับซ้อน) dbpedia-tr:P_(karmaşıklık) dbpedia-uk:Клас_складності_P dbpedia-vi:P_(độ_phức_tạp) dbpedia-zh:P_(複雜度) http://g.co/kg/m/030dh2 http://babelnet.org/rdf/s03506566n http://ma-graph.org/entity/134026603
Wikipage page ID	6881544 (xsd:integer)
Wikipage revision ID	187643425 (xsd:integer)
dbo:wikiPageWikiLink	Depth-first search dbpedia-fr:BPP_(complexité) dbpedia-fr:BQP category-fr:Classe_de_complexité Boolean circuit dbpedia-fr:Classe_de_complexité Horn clause Complete (complexity) Space complexity EXPSPACE EXPTIME Context-free grammar Polynomial hierarchy Theoretical computer science dbpedia-fr:L_(complexité) dbpedia-fr:Langage_creux dbpedia-fr:Logique_modale dbpedia-fr:Logique_temporelle Turing machine dbpedia-fr:Méthodes_de_points_intérieurs dbpedia-fr:NC_(complexité) NL (complexity) NP (complexity) Linear programming dbpedia-fr:P/poly dbpedia-fr:PSPACE dbpedia-fr:Polynôme dbpedia-fr:Problème_NP-complet dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Problème_SAT dbpedia-fr:Problème_de_décision dbpedia-fr:Problème_de_flot_maximum dbpedia-fr:Problème_de_l'évaluation_d'un_circuit dbpedia-fr:Test_de_primalité_AKS dbpedia-fr:Thèse_de_Cobham dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Théorème_de_hiérarchie_en_temps_déterministe dbpedia-fr:Vérification_de_modèles dbpedia-fr:ZPP_(complexité) dbpedia-fr:Mathématiques
page length (characters) of wiki page	11433 (xsd:nonNegativeInteger)
dct:subject	category-fr:Classe_de_complexité
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Langue dbpedia-fr:Modèle:Palette dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Référence_nécessaire dbpedia-fr:Modèle:Voir_homonymes dbpedia-fr:Modèle:Complexity_Zoo dbpedia-fr:Modèle:Computational_Complexity_(Arora_et_Barak)
prov:wasDerivedFrom	wikipedia-fr:P_(complexité)?oldid=187643425&ns=0
foaf:depiction
prop-fr:fin	P#p (fr)
prop-fr:nom	P (fr)
prop-fr:titreChapitre	The computational model —and why it doesn’t matter (fr)
prop-fr:numéroChapitre	1 (xsd:integer)
thumbnail	wiki-commons:Special:FilePath/Complexity_subsets_pspace.svg?width=300
foaf:isPrimaryTopicOf	wikipedia-fr:P_(complexité)
has abstract	La classe P, aussi noté parfois PTIME ou DTIME(nO(1)), est une classe très importante de la théorie de la complexité, un domaine de l'informatique théorique et des mathématiques. Par définition, un problème de décision est dans P s'il est décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème est décidé en temps polynomial. Les problèmes dans P sont considérés comme « faisables » (feasible en anglais), faciles à résoudre (dans le sens où on peut le faire relativement rapidement). C'est la thèse de Cobham émise par le scientifique américain Alan Cobham. René Lalement attribue cette thèse à Cook. La classe P est incluse dans la classe NP, conduisant à l'un des grands problèmes ouverts de la théorie de la complexité, à savoir : P est-il égal à NP ? (fr)

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 11 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software