준회원권

수학 및 이론 컴퓨터 과학에서 세트의 반회원 문제는 두 가지 가능한 요소 중 어떤 요소가 그 세트에 속할 가능성이 더 높은지를 결정하는 문제로서, 또는 적어도 한 요소가 세트에 있는 두 가지 요소를 고려하여 구성원과 비회원을 구별하는 것이다.

준회원권 문제는 회원권 문제보다 훨씬 쉬울 수 있다.예를 들어, 일부 고정 실수 x보다 작은 dynadic rationals를 나타내는 유한 길이 이진 문자열의 S(x)를 고려하십시오.한 쌍의 끈에 대한 준회원 문제는 더 작은 이치를 나타내는 끈을 취함으로써 해결되는데, 그 끈 중 하나가 정확히 요소라면 x의 가치에 관계 없이 더 작은 것이어야 하기 때문이다.그러나 S(x)는 헤아릴 수 없이 그러한 x가 많지만 c에만 있기 때문에, 언어 S(x)는 재귀 언어가 아닐 수도 있다.어림도 없이 많은 재귀 언어

순서가 지정된 쌍(x,y)의 함수 f는 f(x,y)가 x 또는 y와 같고 f(x,y)가 x 중 하나 이상일 때마다 s에 있으면 s 집합의 선택기이다.집합은 재귀 선택기가 있는 경우 반재귀성이며, 다항 시간 선택기가 있는 경우 P 선택형 또는 반실행형이다.

반감기 세트는 작은 회로를 가지고 있고, 그것들은 확장된 낮은 계층 구조 안에 있으며, P=NP가 아니면 NP 완성될 수 없다.

참조

• 데릭 데니 브라운, "Semi-memberhip algorithm: 최근 발전", 기술 보고서, 컴퓨터 과학 대학 로체스터 학부, 1994
• 레인 A. 헤마스파안드라, 오기하라 미쓰노리, 복잡성 이론 동반자, 이론 컴퓨터 과학의 텍스트, EATCS 시리즈, 스프링거, 2002, ISBN3-540-67419-5, 페이지 294
• 레인 A. 헤마스파안드라, 리엔 토렌블리에트, "반실용 알고리즘의 이론", 이론 컴퓨터 과학의 모노그래프, 스프링거, 2003, ISBN 3-540-42200-5, 1페이지
• Ker-I Ko, Ronald V의 " 이산 복잡성 이론의 기술을 수치 계산에 적용".책(ed.), "복잡성 이론의 연구", 이론 컴퓨터 과학 연구 노트, Pitman, 1986, ISBN 0-470-20293-9, 페이지 40
• C. Jockusch jr (1968). "Semirecursive sets and positive reducibility" (PDF). Trans. Amer. Math. Soc. 137: 420–436.