[ Concept ] P NP 문제

P 분류(P class)

판정 문제들을 분류하는 방법 중 하나

• 판정 문제: 입력 값에 대해 예 / 아니오 답을 내릴 수 있는 문제

결정론적 튜링 기계에서 다항식 시간 안에 풀 수 있는 모든 문제를 포함

결정론적 튜링기계란?튜링 기계: 무언가를 계산하는 기계를 대표하는 가상의 장치 일반적인 컴퓨터 알고리즘을 수행할 수 있음결정론적 튜링 기계 어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정됨 코어 하나에서 명령어를 순서대로 실행한다 생각할 것 즉, 코어 하나에서 실행되는 다항식 시간 알고리즘이 있는 문제는 P

NP 분류(NP class)

NP: 비결정적 다항식 시간(Nondeterministic Polyormial Time)

• Not P가 아님(매우 중요함)

비결정론적 튜링 기계어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정되지 않음 여러 개의 다음 명령어를 병렬적으로 실행하는 기계라고 생각하면 됨

결정론적 튜링 기계에서의 NP 문제

• 일단 답이 있으면 그 답이 맞는지를 다항식 시간 안에 검증할 수 있음
• 푸는 데는 지수 시간이 걸릴 수도 있음
  • 그래도 다항식 시간 안에 검증 가능

랜덤 접근 기계는 결정론적 튜링 기계

• 랜덤 접근 기계: 레지스터를 갖춘 CPU 1개
• 앞으로 별도 언급이 없으면 결정론적 튜링 기계를 의미
• NP 문제를 일반적인 방법으로 풀기에는 좀 느림
  • 대신 무작위, 근사, 휴리스틱 알고리즘 등을 이용

다음 프로그램은 P? NP?

public static boolean hasGreater(int[] nums, int k){
	for (int i =0; i< nums.length; ++i){
		if(nums[i] > k){
			return true;
		}
	}
	return false;
}

P 또는 NP가 아님!

• 둘 사이의 판단 기준이 아예 다름
  • NP가 not P가 아님
• 사실 모든 P 문제는 NP

NP - 완전(NP-complete, NPC) 문제

• NP 문제중 일부
• 모든 NP 문제들은 NP - 완전 문제로 환원 가능
  • 그것도 다항식 시간 안에
  • 여전히 NP 문제이니 다항식 시간 안에 답 검증 가능
• 최소 다른 NP문제들만큼 어려운 문제
• 따라서 NP 중에서도 가장 어려운 문제라고 할 수 있음

NP 완전 문제의 예

• 외판원 문제(판정 버전)
  • 어떤 정해진 길이 L이 있음
  • 이 길이를 넘지 않는 경로가 있는지 판정
  • 나중에 그래프 배우면서 봄
• 배낭 문제(knapsack) 문제
  • 크기와 가격이 다른 여러 물품이 있음
  • 값어치가 최대가 되도록 물건 넣기
  • 당연히 배낭에는 크기 제한이 있음
  • 판정 버전: 최소 어떤 값어치 V만큼 넣을 수 있는가?
    • 약한 NP - 완전 문제: 의사 다항식 시간 안에 풀 수 있음
• 해법은 나중에 배움
  • 동적 계획법(dynamic programming)
  • 그리디(greedy) 알고리즘

NP - 난해(NP - hard) 문제

• 최소 NP - 완전 문제만큼 어려운 문제들
• NP - 완전 문제는 모두 NP - 난해 문제
• NP가 아닌 문제도 있음
  • 즉, 다항식 시간에만 답 검증이 불가능한 문제
  • 당연히 NP보다 복잡도가 높은 문제

P vs NP 문제

• P 또는 NP냐를 논하는 문제가 아님
• P와 NP가 같은지 아닌지를 논하는 문제

P =NP vs P != NP

• NP - 완전 문제는 NP문제 중 가장 어려운 문제
• NP - 완전 문제 중 하나라도 다항식 시간 안에 풀 수 있다면?
  • 이 문제는 P가 됨
  • 모든 NP 문제를 NP - 완전 문제로 다항식 시간 안에 환원할 수 있음
  • 따라서 모든 NP 문제가 P가 됨(P = NP)
• P = NP가 되면 디지털 사회에 미치는 여파는?
  • 느려서 못 풀던 그 많은 문제를 효율적으로 풀 수 있음