브라우저보다 빠른!
27 처지: BPP, BQP, Co-NP, EXPSPACE, EXPTIME, 데이비드 S. 존슨, 결정 문제, 복잡도 종류 목록, 계산 가능성 이론, 계산 복잡도 이론, 부분집합, 다항 시간, 튜링 기계, 재귀 열거 언어, 점근 표기법, 정규 문법, 추상 기계, 콜모고로프 복잡도, 함수 문제, 확률적 튜링 기계, NC (복잡도), NP (복잡도), NP-완전, P (복잡도), P-완전, PSPACE, PSPACE-완전.
BPP
BPP의 다른 뜻은 다음과 같.
새로운!!: 복잡도 종류와 BPP · 더보기 »
BQP
BQP는 계산 복잡도 이론 용어로 '유계오차 양자 다항시간'(有界誤差 量子 多項時間, Bounded error, Quantum, Polynomial time)의 약자이.
새로운!!: 복잡도 종류와 BQP · 더보기 »
Co-NP
산 복잡도 이론에서 co-NP는 복잡도 종류이.
새로운!!: 복잡도 종류와 Co-NP · 더보기 »
EXPSPACE
산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 \colorBlueO(2^p(n)) 공간을 써서 풀 수 있는 판정 문제의 집합이.
새로운!!: 복잡도 종류와 EXPSPACE · 더보기 »
EXPTIME
산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 \colorBlueO(2^p(n))시간에 풀 수 있는 모든 판정 문제의 집합이.
새로운!!: 복잡도 종류와 EXPTIME · 더보기 »
데이비드 S. 존슨
이비드 스티플러 존슨(David Stifler Johnson, 1945년 12월 9일 ~)은 알고리즘과 최적화 분야에서 유명한 컴퓨터 과학자이.
새로운!!: 복잡도 종류와 데이비드 S. 존슨 · 더보기 »
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
새로운!!: 복잡도 종류와 결정 문제 · 더보기 »
복잡도 종류 목록
이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이.
새로운!!: 복잡도 종류와 복잡도 종류 목록 · 더보기 »
계산 가능성 이론
산 가능성 이론(計算可能性理論) 또는 재귀 이론(再歸理論)은 수학기초론의 중요한 분야이자 컴퓨터 과학에서는 계산 이론의 한 갈래이.
새로운!!: 복잡도 종류와 계산 가능성 이론 · 더보기 »
계산 복잡도 이론
산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.
새로운!!: 복잡도 종류와 계산 복잡도 이론 · 더보기 »
부분집합
부분집합 관계를 표현한 벤 다이어그램. ''A''는 ''B''의 부분집합이다. 집합론에서 집합 B의 부분집합(部分集合) A는, 모든 원소가 B에도 속하는 집합이.
새로운!!: 복잡도 종류와 부분집합 · 더보기 »
다항 시간
항 시간(多項時間)은 어떠한 문제를 계산하는 데에 걸리는 시간 m(n)이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 가리.
새로운!!: 복잡도 종류와 다항 시간 · 더보기 »
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
새로운!!: 복잡도 종류와 튜링 기계 · 더보기 »
재귀 열거 언어
재귀 열거 언어(귀납적 가산 언어), 부분 결정성 언어 또는 튜링 수리성 언어는 계산 이론과 수리논리학에서 다루는 형식 언어의 종류로, 문자열의 집합의 재귀 열거인 부분집합이.
새로운!!: 복잡도 종류와 재귀 열거 언어 · 더보기 »
점근 표기법
점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이.
새로운!!: 복잡도 종류와 점근 표기법 · 더보기 »
정규 문법
정규 문법은 정규 언어를 기술하는 형식 문법이.
새로운!!: 복잡도 종류와 정규 문법 · 더보기 »
추상 기계
상기계(抽象機械, abstract machine)는 컴퓨터 하드웨어나 소프트웨어의 이상적인 모형이.
새로운!!: 복잡도 종류와 추상 기계 · 더보기 »
콜모고로프 복잡도
알고리즘 정보이론에서 콜모고로프 복잡도는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의.
새로운!!: 복잡도 종류와 콜모고로프 복잡도 · 더보기 »
함수 문제
산 복잡도 이론에서 함수 문제란 판정 문제가 아닌 문제들, 다시 말해서 답이 예/아니오보다 복잡한 문제들이.
새로운!!: 복잡도 종류와 함수 문제 · 더보기 »
확률적 튜링 기계
확률적 튜링 기계(Probabilistic Turing machine)는 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을.
새로운!!: 복잡도 종류와 확률적 튜링 기계 · 더보기 »
NC (복잡도)
산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이.
새로운!!: 복잡도 종류와 NC (복잡도) · 더보기 »
NP (복잡도)
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.
새로운!!: 복잡도 종류와 NP (복잡도) · 더보기 »
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
새로운!!: 복잡도 종류와 NP-완전 · 더보기 »
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
새로운!!: 복잡도 종류와 P (복잡도) · 더보기 »
P-완전
산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있. 어떤 판정 문제가 P-완전이려면 P에 대해 완전해야.
새로운!!: 복잡도 종류와 P-완전 · 더보기 »
PSPACE
산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이.
새로운!!: 복잡도 종류와 PSPACE · 더보기 »
PSPACE-완전
산 복잡도 이론에서 PSPACE-완전은 복잡도 종류이.
새로운!!: 복잡도 종류와 PSPACE-완전 · 더보기 »
여기로 리디렉션합니다
복잡도류.
