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 는 증명된적이 없음
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
172197 [질문] 박사과정 학위청구논문 과정(논문제출자격) 관련 질문. [7] 개구리농노8382 23/08/19 8382
172196 [질문] 가성비 키보드 질문 겸 추천 좀 부탁드립니다. [6] 여름9441 23/08/19 9441
172195 [질문] 러닝용 스마트 워치 추천 부탁드립니다. [11] 선플러10056 23/08/19 10056
172194 [질문] 최근2년내 재밌는 웹소설 추천받습니다 [16] 모아10227 23/08/19 10227
172193 [질문] 삿포로 징기스칸집 추천가능할까요 [8] 진공묘유7836 23/08/19 7836
172192 [질문] 결혼식때 정장입나요?? [33] 좋습니다9706 23/08/19 9706
172191 [질문] [LOL] 친구와 내기 [2] Arya Stark6759 23/08/19 6759
172190 [질문] SKT 이번에 자급제 플립5로 변경했는데 따로 기기등록 해아할까요? [3] EnzZ7651 23/08/19 7651
172189 [질문] pc에서 앱플레이어 추천해 주세요 [4] 비상하는로그8469 23/08/19 8469
172188 [질문] 방문틀에 철봉 고무자국 없앨 수 있을까요? [7] 크음8081 23/08/19 8081
172187 [질문] 신경외과 유명한데 있을까요 [2] Ika1327084 23/08/19 7084
172186 [질문] 욕실 샤워기 누수인데 어떻게 하는게 좋나요? [10] will9702 23/08/19 9702
172185 [질문] 노트북(엘지 그램) UEFI Boot 로 윈도우 설치가 안됩니다 [3] BlueSKY--7748 23/08/18 7748
172184 [질문] 30대 후반 여자, 탈모증상 [8] 사랑해 Ji9087 23/08/18 9087
172183 [질문] 토스로 주식 하시는 분들 계신가요? 매도 관련 질문인데... [8] 블랙리스트7966 23/08/18 7966
172182 [질문] 디스코드가 초등학생이 원활히 사용할 수 있는 수준인가요? [5] 세종9208 23/08/18 9208
172181 [질문] 할머니 영양제 추천좀 부탁드리겠습니다. [1] 워렌버핏8491 23/08/18 8491
172178 [질문] 요즘 댁에 정수기는 어떤거를 어떻게하시나요? [11] 포커페쑤8197 23/08/18 8197
172177 [질문] 외국인 배우자 공항 입국 심사시 [6] 닝구임다8242 23/08/18 8242
172176 [질문] 노트북 구매 비교 좀 부탁드려요! [2] 늘새로워6876 23/08/18 6876
172175 [질문] 주택 담보 대출 관련 질문입니다 [6] 낭만.로망.갈망7983 23/08/18 7983
172174 [질문] [논란주의]리오넬 메시 눈찢 논란관련 궁금 [13] 먼산바라기9028 23/08/18 9028
172173 [질문] 일반인이 미국 주식시장에 있는 3배 레버리지로 돈을 벌수 없는 이유는 뭔가요? [29] 보리야밥먹자8417 23/08/18 8417
목록 이전 다음
댓글

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