About: Reduction (computability theory)

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Reduction (computability theory) Goto Sponge NotDistinct Permalink

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

http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FReduction_%28computability_theory%29

In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to .

Attributes	Values
rdfs:label	Reduction (computability theory) (en) Redução (teoria da recursão) (pt)
rdfs:comment	In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to . (en) Na Teoria da computação, muitos tipos de reduções são estudadas. A motivação para tal, é a seguinte: dado os conjuntos de números naturais A e B, é possível efetivamente converter um método de decisão para B em um método de decisão para A? Se a resposta para essa questão for positiva, então pode se dizer que A é redutível a B. (pt)
dcterms:subject	Reduction (complexity)
Wikipage page ID	9719800 (xsd:integer)
Wikipage revision ID	1119788903 (xsd:integer)
Link from a Wikipage to another Wikipage	Preorder Enumeration reducibility Reduction (complexity) Peano arithmetic Computability theory Computably enumerable Constructible universe Analytical hierarchy Arithmetical hierarchy Computable set Computational complexity theory Many-one reduction Transitive relation Polynomial-time reduction Church-Turing thesis Halting problem XOR gate Indicator function Injective function Recursive ordinal Reflexive relation Turing jump Post's theorem Turing reduction Partial order Enumerability Turing reducibility Arithmetical reducibility Oracle Turing machine Hyperarithmetical reducibility Decision problems Truth table reduction ZFC set theory
Link from a Wikipage to an external page	http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf https://plato.stanford.edu/entries/recursive-functions/
sameAs	Reduction (computability theory) Reduction (computability theory) Reduction (computability theory)
dbp:wikiPageUsesTemplate	dbt:Main dbt:Other_uses dbt:Isbn
has abstract	In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets and of natural numbers, is it possible to effectively convert a method for deciding membership in into a method for deciding membership in ? If the answer to this question is affirmative then is said to be reducible to . The study of reducibility notions is motivated by the study of decision problems. For many notions of reducibility, if any noncomputable set is reducible to a set then must also be noncomputable. This gives a powerful technique for proving that many sets are noncomputable. (en) Na Teoria da computação, muitos tipos de reduções são estudadas. A motivação para tal, é a seguinte: dado os conjuntos de números naturais A e B, é possível efetivamente converter um método de decisão para B em um método de decisão para A? Se a resposta para essa questão for positiva, então pode se dizer que A é redutível a B. O estudo de noções de redutibilidade é motivado pelo estudo da decisão de problemas. Para noção de muitos problemas de redutibilidade, se algum conjunto não-computável é redutível a um conjunto A, então A deve ser não computável. Isto nos dá uma técnica muito poderosa para provar que muitos conjuntos de problemas são não-computáveis. (pt)
prov:wasDerivedFrom	wikipedia-en:Reduction_(computability_theory)?oldid=1119788903&ns=0
page length (characters) of wiki page	12796 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Reduction_(computability_theory)
is Link from a Wikipage to another Wikipage of	Reduction (recursion theory) Reducibility relation
is Wikipage redirect of	Reduction (recursion theory) Reducibility relation
is foaf:primaryTopic of	wikipedia-en:Reduction_(computability_theory)

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software