브라우저보다 빠른!
17 처지: 로그, 결정 문제, 복잡도 종류, 계산 복잡도 이론, 기댓값, 비결정론적 튜링 기계, 튜링 기계, 크리스토스 파파디미트리우, 유향 그래프, 확률적 튜링 기계, L (복잡도), NC (복잡도), P (복잡도), P-NP 문제, PSPACE, 1994년, 1차 논리.
로그
''e'', 초록색은 밑이 10, 보라색은 밑이 1.7이다. 밑 값에 상관없이 모든 대수 곡선은 (1, 0)을 지난다. 로그()는 수학 함수의 일종으로, 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타내는 함수이.
새로운!!: NL (복잡도)와 로그 · 더보기 »
결정 문제
산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말..
새로운!!: NL (복잡도)와 결정 문제 · 더보기 »
복잡도 종류
복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이.
새로운!!: NL (복잡도)와 복잡도 종류 · 더보기 »
계산 복잡도 이론
산 복잡도 이론(Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연. 이 때 알고리듬의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용.
새로운!!: NL (복잡도)와 계산 복잡도 이론 · 더보기 »
기댓값
확률론에서, 확률 변수의 기댓값(期待값)은 각 사건이 벌어졌을 때의 이득과 그 사건이 벌어질 확률을 곱한 것을 전체 사건에 대해 합한 값이.
새로운!!: NL (복잡도)와 기댓값 · 더보기 »
비결정론적 튜링 기계
비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말. 이것은 비결정론적 유한 오토마타와 유사한 개념이.
새로운!!: NL (복잡도)와 비결정론적 튜링 기계 · 더보기 »
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
새로운!!: NL (복잡도)와 튜링 기계 · 더보기 »
크리스토스 파파디미트리우
리스토스 파파디미트리우 크리스토스 파파디미트리우 (Χρίστος Χαρίλαος Παπαδημητρίου, Christos Harilaos Papadimitriou, 1949년 8월 16일~) 는 UC 버클리의 전산학 교수이.
새로운!!: NL (복잡도)와 크리스토스 파파디미트리우 · 더보기 »
유향 그래프
유향 그래프(有向graph)는 방향을 가진 그래프이.
새로운!!: NL (복잡도)와 유향 그래프 · 더보기 »
확률적 튜링 기계
확률적 튜링 기계(Probabilistic Turing machine)는 비결정론적 튜링 기계의 하나로, 기계의 다음 상태가 확률적으로 정해지는 성질을.
새로운!!: NL (복잡도)와 확률적 튜링 기계 · 더보기 »
L (복잡도)
산 복잡도 이론에서 L(LSPACE 또는 DLOGSPACE)은 결정론적 튜링 기계가 로그 기억 공간을 써서 풀 수 있는 판정 문제의 복잡도 종류이.
새로운!!: NL (복잡도)와 L (복잡도) · 더보기 »
NC (복잡도)
산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이.
새로운!!: NL (복잡도)와 NC (복잡도) · 더보기 »
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
새로운!!: NL (복잡도)와 P (복잡도) · 더보기 »
P-NP 문제
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었.
새로운!!: NL (복잡도)와 P-NP 문제 · 더보기 »
PSPACE
산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이.
새로운!!: NL (복잡도)와 PSPACE · 더보기 »
1994년
1994년은 토요일로 시작하는 평년이.
새로운!!: NL (복잡도)와 1994년 · 더보기 »
1차 논리
1차 논리(一次論理)는 원소에만 한정 기호를 가할 수 있고, 술어에는 한정 기호를 가할 수 없는 술어 논리이.
새로운!!: NL (복잡도)와 1차 논리 · 더보기 »
