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.
For example, consider the set S(x) of finite-length binary strings representing the dyadic rationals less than some fixed real number x.
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.
This theoretical computer science–related article is a stub.