About: Turing reduction

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

Concept in computability theory

Property	Value
dbo:description	concept in computability theory (en) conceito da teoria da computação (pt) concepte en la teoria de la computabilitat (ca)
dbo:wikiPageExternalLink	https://www.cl.cam.ac.uk/teaching/2122/CompTheory/comt-notes.pdf http://projecteuclid.org/download/pdf_1/euclid.bams/1183505800 https://www.cis.upenn.edu/~jean/home.html http://www.ams.org/notices/200610/whatis-davis.pdf https://xlinux.nist.gov/dads/HTML/turingredctn.html
dbo:wikiPageInterLanguageLink	dbpedia-he:רדוקציה_חישובית
dbo:wikiPageWikiLink	dbr:Constructible_universe dbr:Oracle_machine dbr:Polynomial-time_reduction dbr:Smn_theorem dbc:Reduction_(complexity) dbr:Log-space_reduction dbr:Computable_set dbr:Universal_Turing_machine dbr:Many-one_reduction dbr:Preorder dbr:Computable_function dbr:Church–Turing_thesis dbr:Turing_completeness dbr:Equivalence_class dbr:Halting_problem dbr:Turing_jump dbr:Computability_theory dbr:Alan_Turing dbr:Algorithm dbc:Alan_Turing dbr:Arithmetical_set dbr:Computational_complexity_theory dbr:PDF dbr:Function_problem dbr:Turing_degree dbr:Partial_order dbr:P_(complexity) dbr:Undecidable_problem dbr:Notices_of_the_American_Mathematical_Society dbr:Indicator_function dbr:Total_order dbr:Decision_problem dbr:Stephen_Kleene dbr:Emil_Post dbr:Subroutine dbr:Peano_arithmetic dbr:Recursive_ordinal dbr:Recursively_enumerable_set dbr:Mu-recursive_function dbr:Well-founded dbr:Hyperarithmetical_hierarchy dbr:Karp_reduction dbr:Truth_table_reduction
dbp:wikiPageUsesTemplate	dbt:Authority_control dbt:Notelist dbt:Cite_journal dbt:Alan_Turing dbt:Isbn dbt:Efn dbt:Short_description
dct:subject	dbc:Reduction_(complexity) dbc:Alan_Turing
gold:hypernym	dbr:Reduction
rdfs:label	Turing reduction (en) チューリング還元 (ja) Transformacja Turinga (pl) Redução de Turing (pt) Редукция Тьюринга (ru) 圖靈歸約 (zh)
owl:sameAs	freebase:Turing reduction wikidata:Turing reduction dbpedia-zh:Turing reduction dbpedia-ja:Turing reduction dbpedia-pt:Turing reduction dbpedia-fa:Turing reduction dbpedia-ru:Turing reduction dbpedia-pl:Turing reduction http://d-nb.info/gnd/4477590-8 dbpedia-global:Turing reduction dbr:Turing reduction
prov:wasDerivedFrom	wikipedia-en:Turing_reduction?oldid=1286850284&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Turing_reduction
is dbo:knownFor of	dbr:Alan_Turing
is dbo:wikiPageRedirects of	dbr:A-computable dbr:A-recursive_set dbr:Cook_reduction dbr:Co-A-recursive_set dbr:Relative_computability dbr:Turing-reducible dbr:Turing_complete_(reduction) dbr:Turing_complete_set dbr:Turing_completeness_(reduction) dbr:Turing_reducibility dbr:Turing_reducible
is dbo:wikiPageWikiLink of	dbr:Oracle_machine dbr:Polynomial-time_reduction dbr:Simple_set dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Complement_(complexity) dbr:Log-space_reduction dbr:Many-one_reduction dbr:Reductionism dbr:SL_(complexity) dbr:Preorder dbr:Berman–Hartmanis_conjecture dbr:Matroid_oracle dbr:Combinatorial_optimization dbr:Post's_theorem dbr:♯P-complete dbr:Alan_Turing dbr:Algorithm dbr:Martin_measure dbr:PSPACE-complete dbr:Reduction_(complexity) dbr:Sparse_language dbr:List_of_things_named_after_Alan_Turing dbr:Friedberg–Muchnik_theorem dbr:Algorithmically_random_sequence dbr:♯P-completeness_of_01-permanent dbr:Truth-table_reduction dbr:Constant-recursive_sequence dbr:Computability_logic dbr:Computation_in_the_limit dbr:Reduction_(computability_theory) dbr:Polynomial-time_counting_reduction dbr:Legacy_of_Alan_Turing dbr:Enumeration_reducibility dbr:K-trivial_set dbr:Mahaney's_theorem dbr:Hyperarithmetical_theory dbr:A-computable dbr:A-recursive_set dbr:Cook_reduction dbr:Co-A-recursive_set dbr:Relative_computability dbr:Turing-reducible dbr:Turing_complete_(reduction) dbr:Turing_complete_set dbr:Turing_completeness_(reduction) dbr:Turing_reducibility dbr:Turing_reducible
is foaf:primaryTopic of	wikipedia-en:Turing_reduction