R (복잡도)
"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
R (복잡도)는 모든 전역 계산 가능 함수의 집합과 동일하다. 결정 문제는 해당 지표 함수가 계산 가능한 경우에만 R에 속하며, 전역 함수는 해당 함수의 그래프가 R에 속하는 경우에만 계산 가능하다. RE (재귀 열거 가능 집합)와 co-RE (RE의 여집합)의 교집합은 재귀 집합과 같다.
📚 더 읽어볼만한 페이지
-
복잡도 종류 -
P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
-
복잡도 종류 -
P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
2. 동치 공식
재귀 집합 R은 모든 전역 계산 가능 함수의 집합과 동치 관계로 간주된다. 이는 결정 문제의 지표 함수가 계산 가능 함수인지 여부와, 전역 함수의 함수의 그래프가 R에 속하는지 여부를 통해 설명된다.
2.1. 결정 문제
어떤 결정 문제가 있을 때, 그 문제의 지표 함수가 계산 가능하다면, 그 문제는 R에 속한다.
2.2. 전역 함수
전역 함수는 해당 함수의 그래프가 재귀 집합 (R)에 속하는 경우에만 계산 가능 함수이다.
3. 다른 복잡도 클래스와의 관계
재귀 집합(R)은 계산 가능성 이론의 다른 복잡도 종류들과 밀접한 관계를 맺고 있다. 특히, RE와 co-RE의 교집합과 동일하다.
3.1. RE와 co-RE의 교집합
인식기와 공동 인식기가 모두 존재하는 문제는 두 인식기를 번갈아 실행하여 항상 결과를 얻을 수 있다. 따라서 이러한 문제들의 복잡도 종류인 재귀 집합(R)은 RE와 co-RE의 교집합(∩)과 같다.
