About: Oracle machine

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

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:Abstract_machine dbc:Computability_theory dbc:Turing_machine dbr:PSPACE dbr:Robert_M._Solovay dbr:Polynomial_hierarchy dbr:Matroid_oracle dbr:Cryptography dbr:Halting_problem dbr:Arithmetical_hierarchy dbr:Computability_theory dbr:Alan_Turing dbr:Martin_Davis_(mathematician) dbr:Complete_(complexity) dbr:Christos_Papadimitriou dbr:Juris_Hartmanis dbr:Michael_Sipser dbr:Computational_complexity_theory dbr:Boolean_satisfiability_problem dbr:Complexity_class dbr:Function_problem dbr:Kolmogorov's_zero–one_law dbr:DLOGTIME dbr:Space_hierarchy_theorem dbr:Cryptographic_hash_function dbc:Computation_oracles dbr:Random_oracle dbr:Interactive_proof_system dbr:Undecidable_problem dbr:Turing_reduction dbr:Robert_I._Soare dbr:IP_(complexity) dbr:Provable_security dbr:Time_hierarchy_theorem dbr:Turing_machine dbr:Black_box dbr:Indicator_function dbr:Decision_problem dbr:Black_box_group dbr:SIAM_Journal_on_Computing dbr:NP-complete dbr:Polynomial_time dbr:P_=_NP_problem dbr:Hartley_Rogers,_Jr. 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:Cite_web dbt:Main dbt:Reflist dbt:Cite_journal dbt:More_footnotes_needed dbt:Sfn dbt:Original_research_inline dbt:For dbt:Use_dmy_dates dbt:Refend dbt:Div_col dbt:Div_col_end dbt:Refbegin dbt:ProQuest dbt:Cite_thesis dbt:Sfnm dbt:Harvtxt dbt:Black-box dbt:Short_description
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) 神託機械 (ja) Oracle (machine de Turing) (fr) Maszyna Turinga z wyrocznią (pl) 신탁 기계 (ko) 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-fr:Oracle machine dbpedia-tr:Oracle machine dbpedia-zh:Oracle machine dbpedia-ja:Oracle machine dbpedia-pt:Oracle machine dbpedia-he:Oracle machine dbpedia-es:Oracle machine dbpedia-fa:Oracle machine dbpedia-ru:Oracle machine dbpedia-pl:Oracle machine dbpedia-ko:Oracle machine dbpedia-ca:Oracle machine dbpedia-fi:Oracle machine dbpedia-sr:Oracle machine dbpedia-uk:Oracle machine dbpedia-global:Oracle machine dbr:Oracle machine
prov:wasDerivedFrom	wikipedia-en:Oracle_machine?oldid=1294293869&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Oracle_machine
is dbo:wikiPageDisambiguates of	dbr:Oracle_(disambiguation)
is dbo:wikiPageRedirects of	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:Baker-Gill-Solovay_theorem dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles dbr:Machine_oracle dbr:Relativization dbr:Turing_oracle
is dbo:wikiPageWikiLink of	dbr:Chaitin's_constant dbr:BPP_(complexity) dbr:PP_(complexity) dbr:List_of_computability_and_complexity_topics dbr:Norman_Shapiro dbr:S2S_(mathematics) dbr:Proof_of_impossibility dbr:P_versus_NP_problem dbr:God's_algorithm dbr:Deutsch–Jozsa_algorithm dbr:Grover's_algorithm dbr:Formal_methods dbr:Message_authentication_code dbr:Parity_P dbr:Cook–Levin_theorem dbr:Polynomial_hierarchy dbr:Timeline_of_quantum_computing_and_communication dbr:Endgame_tablebase dbr:Oracle_(disambiguation) dbr:Alice_and_Bob dbr:SL_(complexity) dbr:Feistel_cipher dbr:Berman–Hartmanis_conjecture dbr:Matroid_oracle dbr:Descriptive_complexity_theory dbr:Halting_problem dbr:Turing_jump dbr:Arithmetical_hierarchy dbr:Post's_theorem dbr:♯P dbr:Ciphertext_indistinguishability dbr:Probabilistically_checkable_proof dbr:Convex_polytope dbr:Alan_Turing dbr:NP-easy dbr:Complete_(complexity) dbr:Volume dbr:Lance_Fortnow dbr:Property_testing dbr:Quantum_algorithm dbr:Function_problem dbr:List_of_complexity_classes dbr:Induction_puzzles dbr:Large_countable_ordinal dbr:Convex_volume_approximation dbr:Pointclass dbr:Pseudorandom_permutation dbr:Entscheidungsproblem dbr:BQP dbr:Digital_signature dbr:Random_oracle dbr:Interactive_proof_system dbr:Graph_isomorphism_problem dbr:Turing_reduction dbr:Amplitude_amplification dbr:List_of_mathematical_logic_topics dbr:NP-hardness dbr:Admissible_ordinal dbr:Advantage_(cryptography) dbr:IP_(complexity) dbr:Closed-world_assumption dbr:Examples_of_data_mining dbr:Turing_machine dbr:Black_box dbr:Ω-consistent_theory dbr:Garbage_collection_(computer_science) dbr:Block_cipher dbr:Algorithmically_random_sequence dbr:Chosen-plaintext_attack dbr:Circuits_over_sets_of_natural_numbers dbr:Systems_of_Logic_Based_on_Ordinals dbr:Bernstein–Vazirani_algorithm dbr:Hypercomputation dbr:Low_(complexity) dbr:Lattice_problem dbr:Black_box_group dbr:Differential_testing dbr:Generic_group_model dbr:Hidden_subgroup_problem dbr:Quantum_complexity_theory dbr:Polynomial_creativity dbr:Enumeration_reducibility dbr:Geometric_complexity_theory dbr:Hidden_shift_problem dbr:Demand_oracle dbr:PH_(complexity) 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:Baker-Gill-Solovay_theorem dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles dbr:Machine_oracle dbr:Relativization dbr:Turing_oracle
is foaf:primaryTopic of	wikipedia-en:Oracle_machine