Semi-membership (original) (raw)
Berechenbare Ordnungen bezeichnen in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte entscheidbare Relationen.Sie bilden den Ausgangspunkt für semi-berechenbare Mengen sowie für berechenbare Ordinalzahlen.
| Property | Value |
|---|---|
| dbo:abstract | Berechenbare Ordnungen bezeichnen in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte entscheidbare Relationen.Sie bilden den Ausgangspunkt für semi-berechenbare Mengen sowie für berechenbare Ordinalzahlen. (de) In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; alternatively, given two elements of which at least one is in the set, to distinguish the member from the non-member. The semi-membership problem may be significantly easier than the membership problem. For example, consider the set S(x) of finite-length binary strings representing the dyadic rationals less than some fixed real number x. The semi-membership problem for a pair of strings is solved by taking the string representing the smaller dyadic rational, since if exactly one of the strings is an element, it must be the smaller, irrespective of the value of x. However, the language S(x) may not even be a recursive language, since there are uncountably many such x, but only countably many recursive languages. A function f on ordered pairs (x,y) is a selector for a set S if f(x,y) is equal to either x or y and if f(x,y) is in S whenever at least one of x, y is in S. A set is semi-recursive if it has a recursive selector, and is P-selective or semi-feasible if it is semi-recursive with a polynomial time selector. Semi-feasible sets have small circuits; they are in the extended low hierarchy; and cannot be NP-complete unless P=NP. (en) |
| dbo:wikiPageExternalLink | http://www.ams.org/tran/1968-131-02/S0002-9947-1968-0220595-7/S0002-9947-1968-0220595-7.pdf |
| dbo:wikiPageID | 25340011 (xsd:integer) |
| dbo:wikiPageLength | 2718 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 994606889 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Dyadic_rational dbr:Computable_function dbr:Mathematics dbr:Low_and_high_hierarchies dbr:NP-complete dbr:Trans._Amer._Math._Soc. dbr:Theoretical_computer_science dbr:P=NP dbc:Computational_complexity_theory dbr:Recursive_language dbr:Circuit_complexity dbr:Polynomial_time |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:ISBN dbt:Comp-sci-theory-stub |
| dct:subject | dbc:Computational_complexity_theory |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | Berechenbare Ordnungen bezeichnen in der theoretischen Informatik, genauer in der Berechenbarkeitstheorie, bestimmte entscheidbare Relationen.Sie bilden den Ausgangspunkt für semi-berechenbare Mengen sowie für berechenbare Ordinalzahlen. (de) In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; alternatively, given two elements of which at least one is in the set, to distinguish the member from the non-member. Semi-feasible sets have small circuits; they are in the extended low hierarchy; and cannot be NP-complete unless P=NP. (en) |
| rdfs:label | Berechenbare Ordnung (de) Semi-membership (en) |
| owl:sameAs | freebase:Semi-membership wikidata:Semi-membership dbpedia-de:Semi-membership https://global.dbpedia.org/id/4uYeV |
| prov:wasDerivedFrom | wikipedia-en:Semi-membership?oldid=994606889&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Semi-membership |
| is dbo:wikiPageRedirects of | dbr:P-selective dbr:Semi-feasible_function dbr:Semi-recursive dbr:Semirecursive |
| is dbo:wikiPageWikiLink of | dbr:Carl_Jockusch dbr:P-selective dbr:Semi-feasible_function dbr:Semi-recursive dbr:Semirecursive |
| is foaf:primaryTopic of | wikipedia-en:Semi-membership |