NP Complete (1) 썸네일형 리스트형 P VS NP, 다항시간, 지수시간, 결정적 알고리즘, 비결정적 알고리즘 이번 글에서는 P와 NP에 대해 다뤄 보도록 하겠습니다. 솔직히 저도 한글로 되어있던지, 영어로 되어있는 글이든 읽으면서 도대체 무슨 말인가라고 할 정도로 이해가 되지 않더군요. 자꾸 반복해 읽어도 조금 이해가 되는 듯 말 듯 여전히 어려운 개념이지만 같이 공부해 봅시다. P vs NP 만약 다항식 시간(polynomial time) 내 결정적 알고리즘(a deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면 x 는 P의 클래스 안에 있다. 만약 다항식 시간(polynomial time) 내 비결정적 알고리즘(a non-deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional pro.. 이전 1 다음
