mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, 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 rational In mathematics, a dyadic rational or binary rational is a number that can be expressed as a fraction whose denominator is a power of two. For example, 1/2, 3/2, and 3/8 are dyadic rationals, but 1/3 is not. These numbers are important in computer ...

s 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 recursive (or ''decidable'') language is a recursive subset of the Kleene closure of an alphabet. Equivalently, a formal language is recursive if there exists a Turing machine that decides the forma ...

, 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 occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...

selector, and is P-selective or semi-feasible if it is semi-recursive with a

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

selector. Semi-feasible sets have small circuits; they are in the extended low hierarchy; and cannot be

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

unless P=NP.

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