P문제

P문제란?

decision problem으로서 polynomial 시간 내에 결정해야하는 문제이다.

 입력에 따라 문제를 풀기 위해 필요한 시간이 다항식으로 표현될 수 있느냐 없느냐가 관건이다.


*desicion problem : Yes or No 로 답이 바로 나오는 것을 말한다. ex) 밥을 먹었는가?
* polynomial time : 다항식 시간을 말한다.  ex) n, n^2+3n (다항식)