브라우저보다 빠른!
24 처지: 리 대수, 복잡도 종류, 부분집합, 부분집합 합 문제, 비결정론적 튜링 기계, 김양곤, 다항 시간, 스티븐 쿡, 튜링 기계, 클레이 수학연구소, 전북대학교, 존 폰 노이만, 컴퓨터 과학, 컴퓨터 과학의 미해결 문제 목록, 쿠르트 괴델, 수학의 미해결 문제 목록, 시간 복잡도, NP (복잡도), NP-난해, NP-완전, P (복잡도), 12월 24일, 1971년, 2003년.
리 대수
리 대수(Lie代數)는 리 군의 국소적 구조를 나타내는 대수 구조이.
새로운!!: P-NP 문제와 리 대수 · 더보기 »
복잡도 종류
복잡도 종류(複雜度 種類)는 계산 복잡도 이론에서 계산 복잡도에 따라서 문제를 분류한 것이.
새로운!!: P-NP 문제와 복잡도 종류 · 더보기 »
부분집합
부분집합 관계를 표현한 벤 다이어그램. ''A''는 ''B''의 부분집합이다. 집합론에서 집합 B의 부분집합(部分集合) A는, 모든 원소가 B에도 속하는 집합이.
새로운!!: P-NP 문제와 부분집합 · 더보기 »
부분집합 합 문제
부분집합 합 문제(subset sum problem)는 계산 복잡도 이론과 암호학에 관련된 문제로, 유한 개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소를 다 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이.
새로운!!: P-NP 문제와 부분집합 합 문제 · 더보기 »
비결정론적 튜링 기계
비결정론적 튜링 기계(nondeterministic Turing machine, NTM)는 튜링 기계에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말. 이것은 비결정론적 유한 오토마타와 유사한 개념이.
새로운!!: P-NP 문제와 비결정론적 튜링 기계 · 더보기 »
김양곤
양곤(1949년 ~)은 전북대학교 수학 통계정보과학부 교수이.
새로운!!: P-NP 문제와 김양곤 · 더보기 »
다항 시간
항 시간(多項時間)은 어떠한 문제를 계산하는 데에 걸리는 시간 m(n)이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 가리.
새로운!!: P-NP 문제와 다항 시간 · 더보기 »
스티븐 쿡
스티븐 아서 쿡(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 문제라고 부르며, 컴퓨터 과학의 가장 중요한 문제로 밀레니엄 문제 중 하나이기도 하다.
새로운!!: P-NP 문제와 스티븐 쿡 · 더보기 »
튜링 기계
링 기계의 작동 방식을 묘사하는 그림 이론 전산학에서, 튜링 기계()는 긴 테이프에 쓰여있는 여러 가지 기호들을 일정한 규칙에 따라 바꾸는 기계이.
새로운!!: P-NP 문제와 튜링 기계 · 더보기 »
클레이 수학연구소
이 수학연구소()는 미국 매사추세츠 주 케임브리지 지방에 있는 사설 비영리 재단이며, 수학을 널리 알리고 발전시키는 활동을 하고 있. 여러 상을 제정해서 유망한 수학자들에게 수여하고 있. 이 연구소는 1998년 제정 지원을 맡은 사업가 랜던 클레이(Landon T. Clay)와 하버드 대학교의 아서 재피에 의해서 설립되었.
새로운!!: P-NP 문제와 클레이 수학연구소 · 더보기 »
전북대학교
전북대학교(全北大學校, Chonbuk National University)는 전라북도 전주시에 소재한 대한민국의 지방거점 국립대학교이.
새로운!!: P-NP 문제와 전북대학교 · 더보기 »
존 폰 노이만
존 폰 노이만(1903년 12월 28일 - 1957년 2월 8일)은 헝가리 출신 미국인 수학자이.
새로운!!: P-NP 문제와 존 폰 노이만 · 더보기 »
컴퓨터 과학
학()은 전산 이론, 하드웨어 및 소프트웨어에 중점을 둔 정보과학의 한 분야이.
새로운!!: P-NP 문제와 컴퓨터 과학 · 더보기 »
컴퓨터 과학의 미해결 문제 목록
음은 컴퓨터 과학의 주요 미해결 문제를 정리한 것이.
새로운!!: P-NP 문제와 컴퓨터 과학의 미해결 문제 목록 · 더보기 »
쿠르트 괴델
르트 괴델(1906년 4월 28일 ~ 1978년 1월 14일)은 불완전성의 정리로 유명한 수학자이자 논리학자이.
새로운!!: P-NP 문제와 쿠르트 괴델 · 더보기 »
수학의 미해결 문제 목록
Science Unsolved problems in: Note: Use the unsolved tag:, where "F" is any field in the sciences: and "X" is a concise "explanation" with or without links.
새로운!!: P-NP 문제와 수학의 미해결 문제 목록 · 더보기 »
시간 복잡도
산 복잡도 이론에서 시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리.
새로운!!: P-NP 문제와 시간 복잡도 · 더보기 »
NP (복잡도)
NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이.
새로운!!: P-NP 문제와 NP (복잡도) · 더보기 »
NP-난해
NP-난해, NP-hard는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이.
새로운!!: P-NP 문제와 NP-난해 · 더보기 »
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
새로운!!: P-NP 문제와 NP-완전 · 더보기 »
P (복잡도)
P(PTIME 또는 DTIME(nO(1)))는 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제를 모아 놓은 복잡도 종류이.
새로운!!: P-NP 문제와 P (복잡도) · 더보기 »
12월 24일
12월 24일은 그레고리력으로 358번째(윤년일 경우 359번째) 날에 해당.
새로운!!: P-NP 문제와 12월 24일 · 더보기 »
1971년
1971년은 금요일로 시작하는 평년이.
새로운!!: P-NP 문제와 1971년 · 더보기 »
2003년
2003년은 수요일로 시작하는 평년이.
새로운!!: P-NP 문제와 2003년 · 더보기 »
