About: Oracle machine

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Abstract machine used to study decision problems

Property	Value
dbo:description	Maschine in der theoretischen Informatik (de) abstract machine used to study decision problems (en) מכונה מופשטת המשמשת במדעי המחשב (iw) abstraktni stroj, ki se uporablja za proučevanje problemov odločanja (sl) tipus de màquina abstracta per estudiar problemes de decisió (ca)
dbo:wikiPageExternalLink	http://citeseer.ist.psu.edu/282397.html
dbo:wikiPageWikiLink	dbr:Robert_I._Soare dbr:Hartley_Rogers,_Jr. dbr:Cryptographic_hash_function dbc:Computability_theory dbr:Alan_Turing dbr:Cryptography dbr:Turing_machine dbr:Turing_reduction dbr:Arithmetical_hierarchy dbr:Abstract_machine dbr:PSPACE dbr:Computational_complexity_theory dbr:Black_box dbr:Boolean_satisfiability_problem dbr:Robert_M._Solovay dbr:Random_oracle dbr:Decision_problem dbr:IP_(complexity) dbr:Complexity_class dbr:Halting_problem dbr:Black_box_group dbr:Indicator_function dbr:Provable_security dbr:Christos_Papadimitriou dbr:Interactive_proof_system dbr:Juris_Hartmanis dbr:Martin_Davis_(mathematician) dbr:Michael_Sipser dbr:Polynomial_hierarchy dbr:DLOGTIME dbr:SIAM_Journal_on_Computing dbr:Computability_theory dbr:Function_problem dbr:Kolmogorov's_zero–one_law dbr:Complete_(complexity) dbr:Polynomial_time dbr:Time_hierarchy_theorem dbr:Undecidable_problem dbc:Turing_machine dbr:Matroid_oracle dbc:Computation_oracles dbr:Space_hierarchy_theorem dbr:NP-complete dbr:P_=_NP_problem dbr:Deterministic_Turing_machine
dbp:1a	Soare (en)
dbp:1p	47 (xsd:integer)
dbp:1y	1987 (xsd:integer)
dbp:2a	Rogers (en)
dbp:2p	130 (xsd:integer)
dbp:2y	1967 (xsd:integer)
dbp:wikiPageUsesTemplate	dbt:Cite_book dbt:Black-box dbt:Cite_journal dbt:Cite_thesis dbt:Cite_web dbt:Div_col dbt:Div_col_end dbt:For dbt:Harvtxt dbt:Main dbt:More_footnotes_needed dbt:Original_research_inline dbt:ProQuest dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Sfnm dbt:Short_description dbt:Use_dmy_dates
dct:subject	dbc:Computability_theory dbc:Turing_machine dbc:Computation_oracles
gold:hypernym	dbr:Machine
rdfs:label	Oracle machine (en) Màquina oracle (ca) Orakel-Turingmaschine (de) Máquina oráculo (es) Oracle (machine de Turing) (fr) 神託機械 (ja) 신탁 기계 (ko) Maszyna Turinga z wyrocznią (pl) Máquina oráculo (pt) Пророча машина (uk) Вычисления с оракулом (ru) 預言機 (zh)
owl:sameAs	freebase:Oracle machine yago-res:Oracle machine wikidata:Oracle machine dbpedia-de:Oracle machine dbpedia-es:Oracle machine dbpedia-pl:Oracle machine dbpedia-tr:Oracle machine dbpedia-fr:Oracle machine dbpedia-he:Oracle machine dbpedia-ja:Oracle machine dbpedia-pt:Oracle machine dbpedia-ru:Oracle machine dbpedia-zh:Oracle machine dbpedia-ko:Oracle machine dbpedia-ca:Oracle machine dbpedia-fa:Oracle machine dbpedia-fi:Oracle machine dbpedia-sr:Oracle machine dbpedia-uk:Oracle machine dbpedia-global:Oracle machine
prov:wasDerivedFrom	wikipedia-en:Oracle_machine?oldid=1300111098&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Oracle_machine
is dbo:wikiPageDisambiguates of	dbr:Oracle_(disambiguation)
is dbo:wikiPageRedirects of	dbr:Baker-Gill-Solovay_theorem dbr:Machine_oracle dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles dbr:Oracle_(complexity) dbr:Oracle_(computability) dbr:Oracle_(computer_science) dbr:Oracle_(computing) dbr:Oracle_Machines dbr:Oracle_Turing_machine dbr:Oracle_algorithm dbr:Oracle_set dbr:Oracle_tape dbr:Relativization dbr:Turing_oracle
is dbo:wikiPageWikiLink of	dbr:God's_algorithm dbr:Endgame_tablebase dbr:Chosen-plaintext_attack dbr:Block_cipher dbr:Deutsch–Jozsa_algorithm dbr:Examples_of_data_mining dbr:Alan_Turing dbr:Turing_machine dbr:Turing_reduction dbr:Arithmetical_hierarchy dbr:Alice_and_Bob dbr:Closed-world_assumption dbr:Hypercomputation dbr:Property_testing dbr:Black_box dbr:Random_oracle dbr:Oracle_(disambiguation) dbr:Convex_polytope dbr:Quantum_complexity_theory dbr:IP_(complexity) dbr:Lattice_problem dbr:Formal_methods dbr:BPP_(complexity) dbr:Halting_problem dbr:Black_box_group dbr:Volume dbr:Ω-consistent_theory dbr:Digital_signature dbr:P_versus_NP_problem dbr:Timeline_of_quantum_computing_and_communication dbr:Amplitude_amplification dbr:Bernstein–Vazirani_algorithm dbr:Entscheidungsproblem dbr:Grover's_algorithm dbr:Interactive_proof_system dbr:Lance_Fortnow dbr:Norman_Shapiro dbr:Polynomial_hierarchy dbr:NP-hardness dbr:Descriptive_complexity_theory dbr:Message_authentication_code dbr:List_of_complexity_classes dbr:Probabilistically_checkable_proof dbr:Berman–Hartmanis_conjecture dbr:Cook–Levin_theorem dbr:Feistel_cipher dbr:BQP dbr:NP-easy dbr:PH_(complexity) dbr:Parity_P dbr:Pointclass dbr:Admissible_ordinal dbr:Post's_theorem dbr:S2S_(mathematics) dbr:Quantum_algorithm dbr:Algorithmically_random_sequence dbr:Garbage_collection_(computer_science) dbr:Ciphertext_indistinguishability dbr:♯P dbr:Generic_group_model dbr:Graph_isomorphism_problem dbr:Induction_puzzles dbr:Chaitin's_constant dbr:Function_problem dbr:Complete_(complexity) dbr:Large_countable_ordinal dbr:PP_(complexity) dbr:Advantage_(cryptography) dbr:List_of_computability_and_complexity_topics dbr:List_of_mathematical_logic_topics dbr:Proof_of_impossibility dbr:Hidden_subgroup_problem dbr:Low_(complexity) dbr:SL_(complexity) dbr:Circuits_over_sets_of_natural_numbers dbr:Matroid_oracle dbr:Pseudorandom_permutation dbr:Systems_of_Logic_Based_on_Ordinals dbr:Geometric_complexity_theory dbr:Turing_jump dbr:Polynomial_creativity dbr:Enumeration_reducibility dbr:Demand_oracle dbr:Convex_volume_approximation dbr:Differential_testing dbr:Hidden_shift_problem dbr:Baker-Gill-Solovay_theorem dbr:Machine_oracle dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles dbr:Oracle_(complexity) dbr:Oracle_(computability) dbr:Oracle_(computer_science) dbr:Oracle_(computing) dbr:Oracle_Machines dbr:Oracle_Turing_machine dbr:Oracle_algorithm dbr:Oracle_set dbr:Oracle_tape dbr:Relativization dbr:Turing_oracle
is foaf:primaryTopic of	wikipedia-en:Oracle_machine