PGR21.com 배너 1

- 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 는 증명된적이 없음
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
172031 [질문] 8월 11 9시 30분 인천공항 비행편의 운명은 어떻게 될까요 [7] ComeAgain7193 23/08/08 7193
172030 [질문] [LOL] 지금 진행중인 플옵 1경기부터 쭉이어서 볼수 있나요? [4] Arya Stark8667 23/08/08 8667
172029 [질문] 수영을 러닝 5km 30분 페이스 정도로 한다고 하면...... [7] 마르키아르6908 23/08/08 6908
172027 [삭제예정] 아이패드의 충전 효율이 매우 낮아졌고 배터리 소모가 빨라졌습니다. 교체해야 할까요? [10] 삭제됨6166 23/08/08 6166
172026 [질문] 아마존 계정을 해킹당했습니다. [2] 따루라라랑7722 23/08/08 7722
172025 [질문] 정도전 요동정벌 관련 질문입니다 [9] 뵈미우스5695 23/08/08 5695
172024 [질문] 액세스포인트와 라우터 [6] 적막5857 23/08/08 5857
172023 [질문] 노트북에는 왜 파워서플라이가 없나요? [13] 늘새로워7333 23/08/08 7333
172022 [질문] 어테뉴에이터, 가변저항기? [1] 흰둥6080 23/08/08 6080
172021 [질문] 갤럭시워치로 카톡 메시지 확인 속도 어떠신가요?? [5] 개미7828 23/08/08 7828
172020 [질문] 메일의 첨부파일 [2] 어...6393 23/08/08 6393
172019 [질문] 노트북 재추천 부탁 드립니다 [2] khia8866 23/08/08 8866
172018 [질문] 아크샨 무한 e 끊을수 있는 방법 질문합니다. [12] 종말메이커8380 23/08/07 8380
172017 [질문] 유튜브 어플 킬 때 화면이 이상한데요 [2] Rays10035 23/08/07 10035
172016 [질문] 유머게시판 음식탭 업로드 관련건 [4] 소시7394 23/08/07 7394
172015 [질문] KTX 승차권 변경 질문입니다. [7] 아르키메데스8548 23/08/07 8548
172014 [질문] 하드디스크의 고장에 병원 CT장비가 연관이 있을까요? [3] 얼티멧클론8878 23/08/07 8878
172013 [질문] 젤님버스25 운동화 인터넷 구매 관련 질문입니다 [12] 개떵이다9659 23/08/07 9659
172012 [질문] 전세만기전 집주인요청 이사할경우 복비+이사비 금액 어느정도 일까요? [19] HesBlUe12077 23/08/07 12077
172011 [질문] 심심한데 읽을 책이나 보고서 추천 부탁드립니다. [11] 사람되고싶다9779 23/08/07 9779
172010 [삭제예정] 정신과 진료를 생각 중인데요...조언 부탁드립니다. [6] 삭제됨8505 23/08/07 8505
172009 [질문] 항공권 가격 문의 [6] Gotetz6894 23/08/07 6894
172008 [질문] 법인카드 법인계좌 왜 되고 안 되고? [9] nmcpvwe8594 23/08/07 8594
목록 이전 다음
댓글

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