P-NP 문제 편집하기

수학 7대 난제인 [[밀레니엄 문제]] 중에 하나

[http://gall.dcinside.com/board/view/?id=etc_entertainment2&no=3079056 사실 존나 쉽게 풀 수 있다]

컴퓨터를 사용해서 문제를 풀 때 문제가 쉽게 풀리면 P 문제, 어렵게 풀리면 NP 문제다. 여기서 쉽냐 어렵냐의 기준은 보통은 시간이 얼마나 걸리냐를 기준으로 한다.

P-NP 문제는 이 쉽게 풀리는 P문제와 쉽게 풀리지 않는 NP 문제가 같은 집합인지 아닌지를 묻는 문제이다. 즉 P=NP라면 어렵게 풀리는 (시간이 오래 걸리는) 문제들도 쉽게 풀 수 있다(시간이 짧게 걸린다) 는 뜻이 되고 P≠NP 라면 그렇지 않다는 뜻이 된다.

언뜻 보면 당연히 P≠NP인게 맞는 것 같지만 진짜로 그런가는 아직도 증명이 안되었다. 할거 없으면 이런거 하나 증명해라. 100만달러 준다.

[[분류:수학]]