P and NP
( Polynomial time and Nondeterministic polynomial time)
속도를 분석할 때 n 이라는 변수에 붙은 지수가 1 이나 2 처럼 미리 정해진 값, 즉 상수 (constant) 로 표현되는 경우에는 그 알고리즘을 '쉬운' 문제라고 간주한다. 지수의 값이 아무리 크다고 해도 그것이 미리 정해진 상수 값이라면 그 알고리즘은 컴퓨터가 적당한 시간 안에 계산해 낼 수 있는 쉬운 알고리즘에 해당하는 것이다. 이렇게 변수위에 붙은 지수가 미리 정해진 상수인 수학 공식을 우리는 (중, 고등학교에서 수학에서 이미 배운 바와 같이) 다항식 (polynomial) 이라고 부른다. 다음은 다항식의 예다. ........ 2n3 x n2 -3
복잡성 이론에서 다항식의 반대말은 '지수 함수 (exponential function)'다 (고등학교 수학에서는 지수함수의 반대말은 로그함수였다). 지수함수란 변수 위에 붙은 지수가 미리 정해져 있는 상수 값이 아니라 그 자신도 변수로 표현되는 함수를 의미한다. 다음은 지수함수의 예다 ......... 2n
......... 복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P' 라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP' 라고 부른다. 여기서 P 는 Polynomial (다항식) 의 머리 글자고, NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자를 의미한다. 이때 NP 가 non-polynomial (비다항식) 을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간내에 해결할 수 있는 문제기 때문에 P 에 속한 문제들은 '쉬운' 문제들이고, NP 는 그와 반대로 '어려운' 문제를 의미한다.
복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP 에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제증의 하나로 통하고 있다. ........... (임백준 2003)
만일 P = NP 이라면, P 는 NP 와 NP-complete 영역을 포함할 것이다.
term :
계산이론 (Theory of Computation) 계산 복잡도 이론 (Computational Complexity Theory) 비결정 완전 (NP-complete) 비결정 난해 (NP-hard) 다항식과 비결정다항식 (P and NP)
site :
Wikipedia : Complexity classes P and NP
paper :
video :
컴퓨터과학이 여는 세계 - P 클래스와 NP 클래스 문제의 개념 : SNU : 이광근 : 2016/03/07 ... 동영상 82개