UP (복잡도)
"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
| 정의 | 비결정적 튜링 기계가 다항 시간 내에 풀 수 있는 문제의 복잡도 종류이지만, 수락 계산 경로는 오직 하나만 존재해야 함. |
|---|
| 별칭 | 단일 P, 모호하지 않은 NP |
|---|
| 클래스 | 복잡도 종류 |
|---|
| 상위 집합 | NP |
|---|
| 하위 집합 | P |
|---|
| 포함 관계 | P ⊆ UP ⊆ NP |
|---|
| 중요 특징 | 비결정적 선택에서 오직 하나의 계산 경로만이 수락 상태로 도달해야 함. |
|---|
| 의미 | 문제의 해가 유일하게 존재함을 보장하는 복잡도 종류. |
|---|
📚 더 읽어볼만한 페이지
-
복잡도 종류 -
P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
-
복잡도 종류 -
P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
