검색 결과

튜링 기계와 그 변종을 기준으로 한다. 점근 표기법은 복잡도를 표기하는 주된 방법이다. 복잡도 종류는 시간 복잡도와 공간 복잡도를 포괄하는 문제의 집합이다. 어떤 복잡도 종류의 정의는 다음과 관련이 있다. 일정 복잡도를 요구하는 추상 기계의 모형. 결정론적 튜링 기계,...

복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이다. 복잡도 종류의 일반적 정의는 다음과 같은 형태로 되어 있다. 예를 들어, NP는 확률적 튜링 기계가 다항시간에 풀 수 있는 판정 문제의 집합이고 PSPACE는 결정론적 튜링 기계가...

P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이다. 선형 계획 제품, 최대공약수 문제 등이 P에 포함되며, 2002년에는 주어진 숫자가 소수인지 판별하는 문제도 P에 속한다는 것이 증명되었다...

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이다. NP에 속하는 문제는 결정론적 튜링 기계로 다항 시간에...

복잡도 이론에서 RP (확률적 다항시간, randomized polynomial time)은 다음과 같은 성질을 만족하는 확률적 튜링 기계가 존재하는 문제들의 복잡도 종류이다. 확률적 튜링 기계의 실행시간은 입력의 크기를 기준으로 다항시간이어야 한다. 실제 결과가 '아니오'일...

알고리즘 정보이론에서 콜모고로프 복잡도(Kolmogorov complexity)는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이...

계산 복잡도 이론에서 복잡도 종류 ZPP(오차 없는 확률적 다항시간, Zero-error Probabilistic Polynomial time)는 다음과 같은 성질을 지니는 확률적 튜링 기계가 존재하는 문제로 이루어진 집합이다. 항상 올바른 '예' 또는 '아니오' 답을...

계산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. NL은 결정론적 튜링 기계에서 로그 공간을 들여 풀 수 있는 문제의 집합인 L을 일반화한...

확률적으로 검사할 수 있는 증명(probabilistically checkable proof)을 할 수 있는 판정 문제들의 복잡도 종류이다. 복잡도 이론에서 PCP 체계는 대화형 증명 체계로 볼 수 있다. 여기에서 증명자(prover)는 무기억 신탁(memoryless...

계산 복잡도 이론에서 UP 곧, 모호하지 않은 비결정론적 다항 시간(Unambiguous non-deterministic Polynomial-time)이란 비결정론적 튜링 기계가 입력마다 받아들이는 경로를 최대 한 개만으로 해서 다항 시간에 풀 수 있는 판정 문제들의...

RE(순환 열거)는 '예' 답변을 튜링 기계로 유한한 시간에 검증할 수 있는 판정 문제의 집합이다. (답변이 '아니오'인 경우에는 기계가 멈추지 않을 수도 있다.) RE는 튜링 기계가 모든 '예' 예제를 낱낱이 열거할 수 있는 결정 문제의 집합이기도 하다. 이 정의는 앞쪽...

계산 복잡도 이론에서 IP(Interactive Polynomial time)는 대화형 증명 체계로 풀 수 있는 문제의 집합이다. 이 시스템의 개념은 골트바서 들이 1985년에 처음 소개하였다. 대화형 증명 체계는 문자열 n {\displaystyle n} 이 어떤 언어에...

계산 복잡도 이론에서 R은 튜링 기계로 풀 수 있는 결정 문제들의 복잡도 종류로, 모든 재귀 언어의 집합과 같다. 또한 R은 모든 전역 계산 가능 함수를 모은 집합과 같으므로 '효율적으로 계산할 수 있는' 함수의 집합으로 볼 수 있어 계산 가능성 이론에서 중요시된다....

계산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을...

계산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이다. 로그 공간은 입력에 대한 포인터 상수개와 이진 플래그 로그 개를 담기에 충분하다는 것을 직관으로 알 수 있다. L을...

이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이다. 다른 계산·복잡도 관련 내용이 궁금하면 계산 가능성과 복잡도 관련 주제 목록을 보자. 복잡도 종류 가운데 원래 종류에 들어 있는 모든 언어의 보완(complement)으로 이루어진 'co'짝이 있는 종류가...

계산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 O ( 2 p ( n ) ) {\displaystyle {\color {Blue}O}(2^{p(n)})} 시간에 풀 수 있는 모든 판정 문제의 집합이다. 여기서 p ( n ) {\displaystyle...

계산 복잡도 이론에서 복잡도 종류 PH는 다항 계층에 있는 모든 복잡도 종류의 합집합이다. PH = ⋃ k ∈ N Δ k P {\displaystyle {\mbox{PH}}=\bigcup _{k\in \mathbb {N} }\Delta _{k}{\mbox{P}}} PH는...

PR은 모든 원시 재귀 함수를 모은 복잡도 종류이다. 동치인 정의로, 단순한 자기 참조 함수로 판정할 수 있는 모든 형식 언어의 집합이라고 할 수도 있다. 단순한 자기 참조 함수에는 덧셈, 곱셈, 거듭제곱, 반복된 거듭제곱 따위가 들어 있다. 아커만 함수는 자기 참조...

계산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이다. 다시 말해서, 어떤 문제가 NC라는 것은, 이 문제를 상수 c {\displaystyle c} 와 k {\displaystyle...