In
mathematics and
theoretical computer science
computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumscribe the ...
, 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
In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the ...
, 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
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
unless
P=NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
.
References
* Derek Denny-Brown, "Semi-membership algorithms: some recent advances", ''Technical report'', University of Rochester Dept. of Computer Science, 1994
* Lane A. Hemaspaandra, Mitsunori Ogihara, "The complexity theory companion", ''Texts in theoretical computer science'', EATCS series, Springer, 2002, , page 294
* Lane A. Hemaspaandra, Leen Torenvliet, "Theory of semi-feasible algorithms", ''Monographs in theoretical computer science'', Springer, 2003, , page 1
* Ker-I Ko, "Applying techniques of discrete complexity theory to numerical computation" ''in'' Ronald V. Book (ed.), "Studies in complexity theory", ''Research notes in theoretical computer science'', Pitman, 1986, , p. 40
*
Computational complexity theory
{{comp-sci-theory-stub