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 는 증명된적이 없음
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
172002 [질문] nvme m.2 ssd 외장 케이스 질문입니다 [2] BlueSKY--8238 23/08/06 8238
172001 [질문] 엑셀 리소스 부족 프리징 현상관련. [4] 비오는일요일6341 23/08/06 6341
172000 [질문] s20 vs s23 구입 질문입니다 [15] 여기7636 23/08/06 7636
171999 [질문] 퇴원 과일바구니 선물 [4] 모찌피치모찌피치7803 23/08/06 7803
171998 [질문] 노트북과 tv모니터연결 [7] 마제스티8194 23/08/06 8194
171997 [질문] 비슷한 형태의 제품 추천바랍니다, 갤럭시 휴대폰 케이스 프로 약쟁이7689 23/08/06 7689
171996 [질문] 컴퓨터가 많이 느려졌습니다 [12] 디아블로48531 23/08/06 8531
171995 [질문] 실내 자전거 추천 부탁드립니다. [2] 동굴곰6609 23/08/06 6609
171994 [질문] 으아악! 내 머리카락이! [6] 형리9642 23/08/06 9642
171993 [질문] 2018 vs 2023 폭염 [43] 바보원두11071 23/08/06 11071
171992 [질문] 데스크탑 모니터 추천부탁드립니당! [5] 냥냥펀치7750 23/08/05 7750
171991 [질문] 대학로 주차 질문입니다. [8] nearby6188 23/08/05 6188
171990 [삭제예정] 노래가 생각이 안나요!! 인디쪽!! 찾아주세요오오오 [16] Janzisuka6515 23/08/05 6515
171989 [질문] 다른 30대분들도 이곳저곳이 고장나시는지요...? [27] 상록일기8994 23/08/05 8994
171987 [질문] 휴대폰 사기를 당한걸까요? [5] LeNTE6900 23/08/05 6900
171986 [질문] 인터넷 속도가 진짜 웃겨요 [9] 반항하는인간7348 23/08/05 7348
171985 [질문] 퍼시스 ch6100, 시디즈 t50 air 의자 쓰시는 분 계신가요 [2] 아재9807 23/08/05 9807
171984 [질문] 뉴욕 숙소에 시계를 놓고 왔는데 심부름센터? 같은게 있을까요 [2] 휵스7891 23/08/05 7891
171983 [질문] 신물질 논문 관련 질문이 드립니다. [14] Paranormal7149 23/08/05 7149
171982 [질문] 부산 해변열차&스카이캡슐 동선 효율 [3] 쑈메7870 23/08/05 7870
171979 [질문] 다나와에서 컴퓨터 구입관련 질문드립니다. [9] 푸른완두콩8559 23/08/04 8559
171978 [질문] 목동운동장 주차질문 [4] 마제스티6781 23/08/04 6781
171976 [질문] 옛날 공포영화 제목 좀 찾아주세요ㅜㅜ [1] 아엠포유7680 23/08/04 7680
목록 이전 다음
댓글

+ : 최근 1시간내에 달린 댓글
+ : 최근 2시간내에 달린 댓글
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기
회원정보 보기
닫기