11 처지: 레오니드 레빈, 미시간 대학교, 스티븐, 튜링상, 충족 가능성 문제, 컴퓨터 과학자 목록, 컴퓨터 과학의 미해결 문제 목록, 쿡-레빈 정리, NC (복잡도), NP-완전, P-NP 문제.
레오니드 레빈
오니드 레빈 레오니드 아나톨리에비치 레빈(1948년 11월 2일 ~)은 소비에트 연방 드네프로페트로프스크(현 우크라이나의 드니프로페트로우스크)에서 출생한 전산학자, 수학자이.
새로운!!: 스티븐 쿡와 레오니드 레빈 · 더보기 »
미시간 대학교
미시간 대학교()는 미국 미시간 주 앤아버에 위치한 연구 중심 공립 대학이.
새로운!!: 스티븐 쿡와 미시간 대학교 · 더보기 »
스티븐
스티븐(Stephen 또는 Steven으로 표기하며 국제 음성 기호의 표기로는 /stiːvən/으로 읽는다)은 그리스어 스테파노스(Στέφανος)에서 파생된 라틴어 이름 스테파누스(Stephanus)에서 다시 파생된 영어권 남성의 이름이.
새로운!!: 스티븐 쿡와 스티븐 · 더보기 »
튜링상
링 상(튜링 어워드)은 ACM에서 컴퓨터 과학 분야에 업적을 남긴 사람에게 매년 시상하는 상이.
새로운!!: 스티븐 쿡와 튜링상 · 더보기 »
충족 가능성 문제
충족 가능성 문제(充足可能性問題, satisfiability problem, SAT)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이.
새로운!!: 스티븐 쿡와 충족 가능성 문제 · 더보기 »
컴퓨터 과학자 목록
이 문서는 컴퓨터 과학자의 목록으로서, 컴퓨터 과학 분야에서 활동한 연구가와 저술가의 목록이.
새로운!!: 스티븐 쿡와 컴퓨터 과학자 목록 · 더보기 »
컴퓨터 과학의 미해결 문제 목록
음은 컴퓨터 과학의 주요 미해결 문제를 정리한 것이.
새로운!!: 스티븐 쿡와 컴퓨터 과학의 미해결 문제 목록 · 더보기 »
쿡-레빈 정리
쿡-레빈 정리(Cook-Levin theorem)는 충족 가능성 문제(SAT)가 NP-완전이라는 것을 증명하는 정리로, 모든 NP 복잡도에 속하는 결정 문제는 다항 시간 내에 충족 가능성 문제로 환산할 수 있다는 것을 의미.
새로운!!: 스티븐 쿡와 쿡-레빈 정리 · 더보기 »
NC (복잡도)
산 복잡도 이론에서 NC(Nick's Class)는 프로세서가 다항 개인 병렬 컴퓨터가 다항로그 시간에 판정할 수 있는 판정 문제의 집합이.
새로운!!: 스티븐 쿡와 NC (복잡도) · 더보기 »
NP-완전
NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.
새로운!!: 스티븐 쿡와 NP-완전 · 더보기 »
P-NP 문제
P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었.
새로운!!: 스티븐 쿡와 P-NP 문제 · 더보기 »