|
:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
23/05/08 12:33
P-NP와 certificate 라는 키워드로 검색하시면 많은 내용들이 나올 겁니다.
P는 Polynomial time 안에 솔루션을 찾을 수 있는 문제이고, NP는 어떤 certificate를 다항 시간 안에 verify 할 수 있는 문제를 이야기합니다. 아주 엄밀한 표현은 아닌데, 헷갈리실까봐 그냥 간단하게 적으면, 어떤 답(혹은 답을 구하기 위한 힌트)을 알고 있을 때, 그 답이 맞는지 아닌지 검증하는 시간이 다항 시간에 들어오면 NP 문제입니다.
23/05/08 14:30
질문이 뭔지 모르겠네요
상상인지 아닌지 궁금하시다는 위 명제라는게 뭘 말하는건지요? P문제는 복잡도가 증가할때 걸리는시간이 polynomial 하게 증가하는 문제입니다 예를들면 n-1개의 식이 있는 n개변수의 방정식 풀이. n이 커질수록 문제를 푸는데 걸리는시간이 증가하지만, n에 비례하게 (즉 polynomial하게) 증가합니다. 즉 P문제는 푸는방식을 알고리듬으로 만들어서 컴퓨터에 돌리면, 아무리 큰 문제라도 웬만하면 다 풀립니다. NP문제는 복잡도가 증가할때 non-polynomial하게 증가하는 문제입니다. n이 늘어나면 n의 제곱이나 세제곱 등으로 시간이 증가하게되면, n이 늘어나면 시간이 어마어마하게 늘어나서, 문제를 푸는 알고리듬을 만들어서 컴퓨터를 돌려도 컴퓨터 뻗을때까지도 답이 안나오는 경우가 많아지죠. P문제와 NP문제는 다르다는것이 증명되었으므로 어떤문제가 NP문제인지 증명하는 방법은, 어떤문제를 조금 바꾸면, 알려진 NP문제가 되는것으로 증명이 가능합니다.
23/05/08 15:35
질문이 명확하지 못했습니다.
질문의 내용을 정리해봤습니다. [어떤 문제의 시간복잡도를 확인하는 문제의 시간복잡도는 어떨까?] 이것입니다! 즉, [어떤 문제가 P문제인지 확인하는 문제] 는 P인가 NP인가 입니다!
23/05/08 15:42
제가 알기로 NP 문제는 복잡도가 non-polynomial 하게 증가하는 문제가 아닙니다..
"제시한 답이 유효한 답인지 P-time 안에 확인할 수 있는 문제" 가 NP 입니다. 그리고 P문제가 NP문제가 다름은 증명되지 않았을걸요.. 밀레니엄 문제인데요 흐흐
|
||||||||||