About: Oracle machine

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

About: Oracle machine Goto Sponge NotDistinct Permalink

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

Attributes	Values
rdfs:label	Màquina oracle (ca) Máquina oráculo (pt) Oracle (machine de Turing) (fr) Oracle machine (en) Вычисления с оракулом (ru) 神託機械 (ja) 預言機 (zh)
rdfs:comment	En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt. Les machines de Turing avec oracle servent notamment à définir la hiérarchie polynomiale ou la hiérarchie arithmétique. (fr)
sameAs	Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine Oracle machine
Wikipage page ID	267793 (xsd:integer)
Wikipage revision ID	167249366 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Calculabilité category-fr:Théorie_de_la_complexité_des_algorithmes Complete (complexity) dbpedia-fr:Décidabilité Arithmetical hierarchy Polynomial hierarchy Turing machine NP (complexity) dbpedia-fr:PSPACE dbpedia-fr:P_(complexité) dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Problème_SAT dbpedia-fr:Problème_de_décision dbpedia-fr:Problème_de_l'arrêt dbpedia-fr:Théorie_de_la_calculabilité dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) Toda's theorem
page length (characters) of wiki page	6053 (xsd:nonNegativeInteger)
dct:subject	category-fr:Calculabilité category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:Langue dbpedia-fr:Modèle:P. dbpedia-fr:Modèle:Pas_clair dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Voir_homonymes dbpedia-fr:Modèle:Ébauche dbpedia-fr:Modèle:Computational_Complexity_(Papadimitriou)
prov:wasDerivedFrom	wikipedia-fr:Oracle_(machine_de_Turing)?oldid=167249366&ns=0
foaf:depiction
thumbnail	wiki-commons:Special:FilePath/Machine_turing_oracle.svg?width=300
foaf:isPrimaryTopicOf	wikipedia-fr:Oracle_(machine_de_Turing)
has abstract	En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt. Les machines de Turing avec oracle servent notamment à définir la hiérarchie polynomiale ou la hiérarchie arithmétique. (fr)
is dbo:wikiPageWikiLink of	Alan Turing Bernstein–Vazirani algorithm Deutsch–Jozsa algorithm dbpedia-fr:Chinois_écrit Complete (complexity) Kolmogorov complexity ElGamal encryption Turing degree E (complexity) dbpedia-fr:Grand_ordinal_dénombrable Polynomial hierarchy Hypercomputation dbpedia-fr:IP_(complexité) dbpedia-fr:Liste_de_classes_de_complexité dbpedia-fr:Liste_de_cryptologues Turing machine dbpedia-fr:NE_(complexité) NP-easy Optimal asymmetric encryption padding Oracle (disambiguation) dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Protocole_Arthur-Merlin dbpedia-fr:RP_(complexité) Toda's theorem dbpedia-fr:Turing dbpedia-fr:Théorème_de_Baker-Gill-Solovay dbpedia-fr:Oracle_(machine_de_turing)
is Wikipage redirect of	dbpedia-fr:Théorème_de_Baker-Gill-Solovay dbpedia-fr:Oracle_(machine_de_turing)
is Wikipage disambiguates of	Oracle (disambiguation) dbpedia-fr:Turing
is oa:hasTarget of	Pt labels Ca labels Ja labels Ru labels En labels Zh labels

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, 5 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software