밀레니엄 문제 중에서 NP문제 질문받는다.

구독자 277명 알림수신 0명 @은월영

왜 부활함

국가안전기획부장 (39.113)

추천 0 비추천 0 댓글 24 조회수 440 작성일 2020-03-06 05:47:55

https://arca.live/b/child/1032063

그렇다. 컴퓨터알고리즘론에서의 오랜 문제였다.

댓글 [24] 글쓰기

aleph

2020-03-06 05:48:58 답글

P는 알겠는데 NP 가 정확히 어떤 건가요

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 05:49:27 삭제 수정 답글

Non-determistic Polynomial 즉, 다항식으로 결정이 불가능하다 이말임 ㅇㅇ

펼쳐보기▼

aleph

2020-03-06 05:49:40 답글

아하

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 05:49:54 삭제 수정 답글

컴퓨터알고리즘 퀴즈에서 절반 이상을 차지하는 바로 back-tracking 문제가 여기에 속한다.

펼쳐보기▼

aleph

2020-03-06 05:50:10 답글

ㄷ

펼쳐보기▼

래커형

2020-03-06 08:19:12 답글

재귀 어렵게 쓰지마욧

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 08:23:40 삭제 수정 답글

재귀랑은 완전히 다른 이야기니까 어렵게 말하는거다;;

펼쳐보기▼

익명_9cGbQ (119.203)

2020-03-06 05:49:38 삭제 수정 답글

NP문제를 모아 놓은 집합은 countable인가요?

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 05:50:15 삭제 수정 답글

결론 : 그 문제 풀 시간에 빨리 자살하세요.

펼쳐보기▼

익명_9cGbQ (119.203)

2020-03-06 05:51:19 삭제 수정 답글

전 NP문제랑 P문제가 수학적으로 엄밀하게 무엇인지 잘 모르겠습니다. 

(그 전에, 컴공에서 문제를 정확히 무엇으로 정의하는지를 모르겟습니다.)

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 05:52:13 삭제 수정 답글

한 마디 요약

P문제 : 식으로 표현 가능
NP문제 : 식으로 표현 불가능 (일명 노가다 해야하고 운빨이 존나 작용하는 문제)

펼쳐보기▼

익명_9cGbQ (119.203)

2020-03-06 05:54:05 삭제 수정 답글

그러면, P 문제를 모아 놓은 집합은 countable인가요?

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 05:54:29 삭제 수정 답글

네 그렇다고 봐야지요. 정확히는 Predictable하다고 보는게 맞다고 봅니다.

펼쳐보기▼

익명_9cGbQ (119.203)

2020-03-06 05:59:42 삭제 수정 답글

말씀하신 predictable 이 혹시 밑 글의 predictable set인가요?

http://www.numdam.org/article/SPS_1990__24__41_0.pdf

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 06:01:02 삭제 수정 답글

??? 거기까지 간건 아닌데요;; 그냥 polynomial하게 표현 가능하니 예측이 가능하다는 겁니다.

펼쳐보기▼

익명_9cGbQ (119.203)

2020-03-06 06:00:35 삭제 수정 답글

P문제에 대해 수학적 정의를 알려 주실 수 있나요?

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 06:01:53 삭제 수정 답글

말 그대로 Polynomial하게 일반적 해를 표현할 수 있는 문제라는 겁니다. 이 이상으로 자세한 정의는 저로써도 어렵네요.

펼쳐보기▼

러시아산홍차

2020-03-06 06:13:13 답글

컴공 교과에서의 중요성을 -10에서 10으로 매겨 주세요

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 06:14:01 삭제 수정 답글

240입니다.

펼쳐보기▼

러시아산홍차

2020-03-06 06:14:15 답글

넵...

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 06:15:30 삭제 수정 답글

이제 저런 NP문제를 알고리즘을 이용해서 잘 해결해내기 위해 노력하는것이 알고리즘론의 최종 목표입니다.

펼쳐보기▼

익명_vTu21 (147.47)

2020-03-06 06:19:32 삭제 수정 답글

"monte carlo"

펼쳐보기▼

국가안전기획부장 (39.113)

2020-03-06 06:20:22 삭제 수정 답글

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

펼쳐보기▼

익명_vTu21 (147.47)

2020-03-06 06:21:38 삭제 수정 답글

*수정됨

이거 가챠각이네 가챠각!
에이 글렀네 글렀어! 가자 아그들아!
가챠각이었는데 까비아깝숑~

펼쳐보기▼

글쓰기

전체글 개념글

최근 최근 방문 채널

최근 방문 채널

전체 잡담 공부 운영

번호 제목

작성자 작성일 조회수 추천

공지 아카라이브 모바일 앱 이용 안내(iOS/Android)

*ㅎㅎ 2020.08.18 29179731

공지 [ 공지 ] 학생 채널 상호 협력 채널

강성호 2020.06.16 2981

나 그라바타 닉 불일치 [1]

홍달수2 2020.03.06 381 0

행렬에 허수가 들어갈수 있나요? [25]

내꿈은건물주 2020.03.06 495 0

밀레니엄 문제 극악이 뭐임?? [4]

홍달수2 2020.03.06 293 0

밀레니엄 문제 학교 시험문제 낼려면 [22]

홍달수2 2020.03.06 474 0

오늘 학원에서 3학년 1학기꺼 끝냈다 [9]

홍달수2 2020.03.06 289 0

코로나 바이러스 덕분에

국가안전기획부장 (39.113) 2020.03.06 221 0

객관식 문제 레벨 [5]

mari 2020.03.06 329 0

강제 홈스쿨링 [7]

HSJ 2020.03.06 493 0

나의 학과 찾기 [4]

전주완주_통합하자 2020.03.06 351 0

저런 진지한 수학이 나올 때 드는 생각 [5]

익명_vTu21 (147.47) 2020.03.06 232 0

푸엥카레 추측은 그래프 이론 알면 이해 쉬움 ㅇㅇ [10]

국가안전기획부장 (39.113) 2020.03.06 336 0

밀레니엄 문제는 괜히 밀레니엄 문제가 아니다. [1]

국가안전기획부장 (39.113) 2020.03.06 117 0

밀레니엄 문제 중에서 NP문제 질문받는다. [24]

국가안전기획부장 (39.113) 2020.03.06 441 0

밀레니엄 문제를 너무 과소평가하네 [9]

aleph 2020.03.06 226 0

수열의 극한의 정의를 고등학교 때 정확하게 알려주면 좋을텐데. [9]

익명_9cGbQ (119.203) 2020.03.06 363 0

난이도 : 밀레니엄 문제 풀기 >> 노벨상 수상 [19]

익명_9cGbQ (119.203) 2020.03.06 423 0

올해는 3모가 아니라 4모네 [2]

홍달수2 2020.03.06 177 0

우리 학교 수학 선생님이나 [20]

홍달수2 2020.03.06 320 0

오늘 아침에 엄빠랑 목욕탕 갔다 [3]

홍달수2 2020.03.06 195 0

아파트에서 원래 공구 소리 내면 [1]

영락제 (39.112) 2020.03.06 226 0

바이러스 더더 심해지나요??

건문3년 (39.112) 2020.03.06 123 0

중2 영어 질문좀 [2]

익명_74GdO (211.36) 2020.03.05 282 -1

민사고 질문받아요 [7]

루카셴카 2020.03.05 290 0

문제집 같은거는 2~3회독 했을때 [3]

익명_xAAFT (122.35) 2020.03.05 276 0

국어 문법 풀어야됨? [8]

홍달수2 2020.03.05 236 0

2018 고1 9모 국어 [11]

홍달수2 2020.03.05 255 0

요즘 바이러스 방역 왜저려냐? [1]

홍무31년 (39.112) 2020.03.05 258 0

저는 민사고 가려고 하는데요... [44]

익명_0jFAk (39.119) 2020.03.05 363 1

P대 NP 문제가 정확히 뭔가요? [3]

익명_9cGbQ (119.203) 2020.03.05 300 0

잘못올림 [1]

aleph 2020.03.05 278 0

글쓰기

전체글 개념글