브라우저보다 빠른!
11 처지: 결정 문제, 계산 복잡도 이론, 교대 튜링 기계, 논리 회로, 스티븐 쿡, 크리스토스 파파디미트리우, L (복잡도), NL (복잡도), NP-완전, P (복잡도), P-완전.
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
새로운!!: NC (복잡도)와 결정 문제 · 더보기 »
계산 복잡도 이론
산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.
새로운!!: NC (복잡도)와 계산 복잡도 이론 · 더보기 »
교대 튜링 기계
링 기계(Alternating Turing machine, ATM)는 비결정론적 튜링 기계에 몇가지 조건이 추가된 기계이.
새로운!!: NC (복잡도)와 교대 튜링 기계 · 더보기 »
논리 회로
전자공학에서 논리 회로는 불 대수를 물리적 장치에 구현한 것으로, 하나 이상의 논리적 입력값에 대해 논리 연산을 수행하여 하나의 논리적 출력값을 얻는 전자회로를 말. AND, OR, NOT의 기본 불 대수를 수행하며, 이 기본 불 대수들의 결합으로 복합적인 논리 기능을 수행.
새로운!!: NC (복잡도)와 논리 회로 · 더보기 »
스티븐 쿡
스티븐 아서 쿡(Stephen Arthur Cook, 1939년 12월 14일~)은 미국의 전산학자이다. 1971년 ACM 《SIGACT Symposium on the Theory of Computing》에 실린 논문 〈The Complexity of Theorem Proving Procedures〉에서 NP-완전의 개념을 확립한 것으로 유명하다. 이 논문에 들어있는 쿡의 정리는 충족 가능성 문제가 NP-완전임을 증명하는 것이다. 이 논문에서 P와 NP가 같은지를 질문했는데 이를 P-NP 문제라고 부르며, 컴퓨터 과학의 가장 중요한 문제로 밀레니엄 문제 중 하나이기도 하다.
새로운!!: NC (복잡도)와 스티븐 쿡 · 더보기 »
크리스토스 파파디미트리우
리스토스 파파디미트리우 크리스토스 파파디미트리우 (Χρίστος Χαρίλαος Παπαδημητρίου, Christos Harilaos Papadimitriou, 1949년 8월 16일~) 는 UC 버클리의 전산학 교수이.
새로운!!: NC (복잡도)와 크리스토스 파파디미트리우 · 더보기 »
L (복잡도)
산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이.
새로운!!: NC (복잡도)와 L (복잡도) · 더보기 »
NL (복잡도)
산 복잡도 이론에서 NL(Nondeterministic Logarithmic-space)은 비결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이.
새로운!!: NC (복잡도)와 NL (복잡도) · 더보기 »
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
새로운!!: NC (복잡도)와 NP-완전 · 더보기 »
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
새로운!!: NC (복잡도)와 P (복잡도) · 더보기 »
P-완전
산 복잡도 이론에서 복잡도 종류 P-완전은 판정 문제의 집합으로, 병렬 컴퓨터가 빠르게 풀 수 있는 문제들을 분석하는 데 쓸모가 있. 어떤 판정 문제가 P-완전이려면 P에 대해 완전해야.
새로운!!: NC (복잡도)와 P-완전 · 더보기 »
