심벌 마크
유니온백과
통신
다운로드하기 Google Play
새로운! 안드로이드 ™에 유니온백과를 다운로드 할 수 있습니다
다운로드
브라우저보다 빠른!
 

NP (복잡도)와 스티븐 쿡

바로 가기: 차이점, 유사점, Jaccard 유사성 계수, 참고 문헌.

NP (복잡도)와 스티븐 쿡의 차이

NP (복잡도) vs. 스티븐 쿡

NP는 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합으로, NP는 비결정론적 다항시간(非決定論的 多項時間, Non-deterministic Polynomial time)의 약자이. 스티븐 아서 쿡(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 문제라고 부르며, 컴퓨터 과학의 가장 중요한 문제로 밀레니엄 문제 중 하나이기도 하다.

NP (복잡도)와 스티븐 쿡의 유사점

NP (복잡도)와 스티븐 쿡는 공통적으로 2 가지를 가지고 있습니다 (유니온백과에서): NP-완전, P-NP 문제.

NP-완전

NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합으로, 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P.

NP (복잡도)와 NP-완전 · NP-완전와 스티븐 쿡 · 더보기 »

P-NP 문제

P는 NP에 속하지만, NP가 P에 속하는지 여부는 밝혀지지 않았다. P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있. 1971년 스티븐 쿡이 그의 논문 〈The Complexity of Theorem Proving Procedures〉(정리 증명 절차의 복잡성)에서 처음으로 제안하였고 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있. 이것은 본래 1956년 쿠르트 괴델이 존 폰 노이만에게 썼던 편지에서 처음으로 언급되었.

NP (복잡도)와 P-NP 문제 · P-NP 문제와 스티븐 쿡 · 더보기 »

위의 목록은 다음 질문에 대한 대답입니다

NP (복잡도)와 스티븐 쿡의 비교.

NP (복잡도)에는 10 개의 관계가 있고 스티븐 쿡에는 18 개의 관계가 있습니다. 그들은 공통점 2을 가지고 있기 때문에, Jaccard 지수는 7.14%입니다 = 2 / (10 + 18).

참고 문헌

이 기사에서는 NP (복잡도)와 스티븐 쿡의 관계를 보여줍니다. 정보가 추출 된 각 기사에 액세스하려면 다음 사이트를 방문하십시오:

이봐 요! 우리는 지금 Facebook에 있습니다! »