PGR21.com
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다.
통합 규정을 준수해 주십시오. (2015.12.25.)
Date 2023/05/08 11:58:46
Name 잘생김용현
Subject [질문] 수학 질문입니다. (P-NP 문제, 시간복잡도 관련)
제가 기억하기로는

[어떤 문제를 푸는 데 걸리는 시간][예상하는 데 드는 시간]은 전자보다 적게 든다고 할 수 없으므로,
문제를 풀기 전, 문제를 푸는 데 얼마나 걸릴지 예상할 수 없다.

라는 증명된 명제가 있는 걸로 기억합니다.

[예상하는 데 드는 시간][검산하는 데 드는 시간] 과는 다른 개념이고
계산시간의 총량을 비교하는 위 명제와 다르게, P-NP 문제는 시간복잡도가 같은지에 관심이 있는 것으로 압니다.


제가 알고있는 지식은 여기까지이고, 질문은 위 명제가 제 상상인건지, 아니면 실제로 있는 명제인지가 궁금합니다.
키워드를 몰라서 구글링을 하기가 어려운데, 혹시 답변 주실 수 있을까요?

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
나일레나일레
23/05/08 12:33
수정 아이콘
P-NP와 certificate 라는 키워드로 검색하시면 많은 내용들이 나올 겁니다.

P는 Polynomial time 안에 솔루션을 찾을 수 있는 문제이고,
NP는 어떤 certificate를 다항 시간 안에 verify 할 수 있는 문제를 이야기합니다.

아주 엄밀한 표현은 아닌데, 헷갈리실까봐 그냥 간단하게 적으면,
어떤 답(혹은 답을 구하기 위한 힌트)을 알고 있을 때, 그 답이 맞는지 아닌지 검증하는 시간이 다항 시간에 들어오면 NP 문제입니다.
잘생김용현
23/05/08 15:34
수정 아이콘
고맙습니다~
마술사
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문제가 다름은 증명되지 않았을걸요.. 밀레니엄 문제인데요 흐흐
사비알론소
23/05/08 20:21
수정 아이콘
이 댓글은 완전 잘못된 댓글입니다.

1. 제곱이건 세제곱이건 다항식임
2. P=NP 는 증명된적이 없음
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
170567 [질문] 스승의날 선물 질문입니다 [1] rDc666968 23/05/10 6968
170566 [질문] RC 카 구매처 관련 문의드립니다. [1] 코지마7466 23/05/10 7466
170564 [질문] 제주도 호텔 추천 [15] 교자만두8835 23/05/10 8835
170563 [질문] 에어콘을 꺼도 실외기가 작동할때 간단하게 진단할요소 [4] Lord Be Goja9218 23/05/10 9218
170562 [삭제예정] 아이폰 위치추적 관련 질문입니다. [4] 공염불7846 23/05/10 7846
170561 [질문] 치아 크라운 빠지면 갔던 치과 가야하나요 [9] 트럭7606 23/05/10 7606
170560 [질문] 영업 하시는 분들 노하우좀 부탁드립니다.. [3] 숴비7471 23/05/10 7471
170559 [질문] s.i.village 살만한 물품 있을까요 [2] 찐타16578 23/05/10 6578
170558 [삭제예정] 의사가 표피낭종 수술 비추천한다하여 질문 드립니다.. [2] 삭제됨7836 23/05/10 7836
170557 [질문] 일본경제관련 유튜브 채널 볼만한곳? [5] 흰둥6868 23/05/10 6868
170556 [질문] 완벽주의의 해악에 대한 책 있을까요? [11] 무한도전의삶6977 23/05/10 6977
170555 [질문] 카니발을 사려면 어떻게 해야하나요? [6] 오타니6668 23/05/10 6668
170554 [질문] 꽃 진드기에 바퀴벌레약 푸들은푸들푸들해7708 23/05/10 7708
170553 [질문] 소규모 국지전이라는게 규모가 다양한가요? [12] Garnett217288 23/05/10 7288
170552 [질문] 부산갑니다 추천부탁드립니다 [6] JSclub9353 23/05/10 9353
170551 [질문] 스팀덱으로 할만한 게임 추천받습니다. [7] 15578999 23/05/10 8999
170550 [질문] 센텀 시티 근처 괜찮은 카페를 찾습니다. [4] Xeri9496 23/05/10 9496
170549 [질문] PP카드나 공항 라운지 이용 가능한 카드 추천 부탁드려요! [4] 11974 23/05/10 11974
170548 [질문] m.2 ssd 추가 후 윈도우 설치 관련 질문입니다. [1] 롤스로이스8259 23/05/09 8259
170547 [질문] 옛날 게임들에 있는 히든 캐릭 고르는 법 같은거는 어떻게 처음 알려지게 되는거였나요? [9] wersdfhr8169 23/05/09 8169
170546 [질문] 혼잣말 하는 버릇 해결방법 [7] 마제스티8531 23/05/09 8531
170545 [질문] 해밀턴 카키필드와 시티즌 pmd56 두 시계 비교의견 [13] Valorant9316 23/05/09 9316
170544 [질문] 디아4 플랫폼 질문 [7] Emiyasiro7847 23/05/09 7847
목록 이전 다음
댓글

+ : 최근 1시간내에 달린 댓글
+ : 최근 2시간내에 달린 댓글
맨 위로