P NP 문제

P NP 문제에 공부하던 중 가장 이해가 잘 되었던 포스팅을 복기하기위한 글입니다.

P, NP 문제 (1) · ratsgo's blog

P/NP 문제에 대해 명철하고 해박하게 서술한 글을 소개해 보겠습니다. 서울대 컴퓨터공학부 이광근 교수님께서 쓰신 컴퓨터 과학이 여는 세계의 일부를 그대로 옮겨 왔습니다. 워낙 좋은 책이라

ratsgo.github.io

P 문제 (p class problem)

현실적(쓸만한)비용으로 해결 가능한 문제들 (polynomial complexity)

문제 해결에 필요한 시간(비용)이 다항시간에 속함

알고리즘 실행비용이 입력 n에 대해 상수 제곱 k의 비용을 가지는 문제를 P문제라고 함

왜 현실적인가?

컴퓨터 성능이 p배 향상되면 입력에 대한 비용이 p배 만큼 줄어듬

비현실적인 문제

exponential complexity를 가진 문제의 경우

p 문제의 n과 k가 바뀌어 주어진 문제의 비용이 상수 k에 대해 n제곱 만큼 필요한 경우

입력이 100만 되어도 k의 100제곱 만큼 비용이 필요

현실 문제에서는 다항함수 중 차수가 얼마나 낮은지 관심이 있음

어렵다를 어떻게 정의할 것인가?

NP 문제 (np class problem, non deterministic problem)

운에 기대면 현실적인 비용으로 해결가능한 문제로 p class 문제를 포함

P = NP, P != NP

P가 NP인지 아닌지는 아직 판별되지 않음

P != NP라면 우리가 풀어야하는 현실의 어려운 문제는 P와 NP의 경계 부근일 것임

P = NP라면 컴퓨터가 현실적인 비용으로 NP문제를 해결할 수 있음

예를 들어, masterpiece에 해당하는 작품을 컴퓨터가 생산할 수 있게 됨

P != NP라면 운에 기대지 않는다면 해결이 어려운 문제가 그 경계일 것

P의 바깥

건너풀기(problem reduction)의 개념 도입

한 단계를 해결하고(종결자) 이를 이용해 목표한 문제를 해결하는 것

건너풀기가 가능하다면 NP complete

그렇지 않다면 NP hard

Friday is awesome.