P-NP 문제

문제의 분류

tractable 풀 수 있다고 증명된 것

• 다항식 문제 인지 확인
• sorting, searching, MST

intractable 풀 수 없다고 증명된 것

• 풀 수 없는데(풀기 쉬운문제, 풀기 어려운문제)
• 정지문제

tractable intractable 한것

• P=NP

P-NP 문제

• P=NP? or P≠NP?
• 다항시간안에 푸는게 불가능하면 intractable하다고 한다

P

• 다항 시간을 가지고 있는 결정 문제

NP

• 다항 시간을 가지고 있는 결정 할수 없는 문제
• 푸는데는 지수시간 검증하는데는 다항시간 걸림

p의 문제점은?

• O(n^3)은 다항 시간이어서(P에 포함된다)
• O(2^n)은 지수시간이 걸린다(NP에 포함된다)

Halting problem(정지문제)

• 어느 입력에도 정지하냐 안하냐?

void loop(int x)
{
	if(x==1)
    	return;
    else
    	while(true);
}

//1을 제외한 모두 정지

int halt(func, cond){
	if (func terminates with cond)
    	return 1; //멈출 수 있음
    else
    	return 0; //멈출 수 없음
}
/* 
halt(loop, x=1)? "yes"
halt(loop, x=0)? "no"
*/

void verify(func){
	if (halt(func, func))
    	loop(0); //멈출 수 없는 함수를 호출
    else
    	loop(1); //멈출 수 있는 함수를 호출
}

verify(verify); //멈출 것이냐, 멈추지 않을 것이냐

P-NP

• NP는 P애 부분 집합인가
  • P=NP? or P≠NP?
• P는 NP의 부분 집합이다

NP이론

• 문제A를 문제B로 변형 가능

CNF-SAT

Clique Problem

• 최적화
  완전그래프
  
• 결정
  ?

Clique문제를 CNF-Satisfiable라는걸 증명하면 NP하다

NP-hard

• 최적치에 근사하게 푼다

BinPacking

• NP-hard하다는 것을 증명
• 근사로 문제를 풀어야한다
• 근사 풀이중 그리디가 가장 좋다(Firtst-fit)이다

유전알고리즘