chap 9. Introduction to the Theory of NP

9.1 Intractability

: 다룰 수 없음
<-> tractability: 다룰 수 있음

 

 

 

Polynomial-Time Algorithm

다항함수와 로그함수만큼의 시간복잡도를 갖는 알고리즘

 

 

 

Polynomial-Time Algorithm으로 풀 수 없는 문제를 

An Intractable Problem이라 한다.

 

 

 

 

9.3 문제의 3가지 카테고리

1. Polynomial-Time algorithm으로 풀 수 있는 문제들

ex)  Sorting, Shortest Paths Problem, Minimum Spanning Tree Problem etc...

 

2. intractable 하다고 증명된 문제들

• polynomial-time이 아닌 걸 증명할 수 있는 문제
  ex) printing all Hamiltonian Circuits, printing all permutations of n keys
• Undecidable problem (컴퓨터로 풀 수 없는 문제)
  ex) Halting Problem

3. intractable 하다고 증명되진 않았지만,  

Polynomial-Time algorithm으로 풀 수 있다고 발견되지 않은 문제들

-> 잘 모르겠는 문제들

ex) -The 0-1 Knapsack Problem,
-The Traveling SalesPerson Problem
-The m-coloring Problem (m > 2)
-Etc.

 

 

 

 

 

9.4 Theory of NP

 

 

Decision Problem

:  yes 또는 no로 답할 수 있는 문제

 

모든 최적화문제를 decision problem으로 바꿀 수 있다.

ex) The Traveling SalesPerson Decision Problem

주어진 d보다 작거나 같은 cost를 갖도록  tour를 할 수 있는지 없는지? 

 

 

 

 

P

: polynomial-time으로 풀리는 모든 decision problem들의 집합

ex) 배열에 특정 key값이 존재하나?

배열이 정렬되었나?

 

TSP decision problem이나 0-1 Knapsack decision problem은 

P인지 알 수 없다.

 

 

 

 

 

Verification

: decision problem의 답이 맞았는지 아닌지 검사하는 과정

 

• false를 리턴했어도 모든 경우에 대한 답을 본 게 아니므로
  decision problem의 답이 no라고 의미하지 않음.
• 검사하는데 Polynomial-time이 걸린다고 해서
  decision problem이 Polynomial-time으로 해결한다고 의미하지 않음.

 

 

 

Nondeterministic Algorithm

: 다음 과정을 따르는 알고리즘

 

1. Guessing : solution을 추측

2. Vertification : 

• true면 끝
• false라면 모든해를 보며 true일 때까지 반복
  -> 무한루프로 돌 수 있다.

 

 

다음과 같은 2가지 상황에서 nondeterministic algorithm “solves” a decision problem라고 말할 수 있다.

-> 1. verification 단계에서 true를 리턴하는 문자열 S가 있을 때 -> answer is "yes"

2. verification 단계에서 true를 리턴하는 문자열 S가 없을 때 -> answer is "no"

 

 

 

 

Polynomial-time nondeterministic algorithm

: verification 단계가 polynomial-time 걸리는 nondeterministic algorithm

 

 

 

 

NP

: polynomial-time nondeterministic algorithm에 의해 solve 할 수 있는 모든  decision problem들의 집합

ex) TSP decision problem

0-1 knapsack decision problem

모든 P에 속하는 문제들 

등등...

 

 

 

 

 

 

 

 

NP-Complete Problems 

 

(Informal하게 정의)

: NP안의 문제들의 부분집합 S가 P에 속한다면, 모든 다른 NP도 P에 속한다.
ex)  TSP를 다항시간동안 풀 수 있다면 모든 NP문제도 다항시간 동안 풀 수 있다.

 

 

 

 

The CNF Satisfiability Problem

 

최초로 NP-complete임을 증명한 문제

Literal: 논리 변수 또는 논리 변수의 부정

Clause: Literal을 or로 결합한 것

Conjunctive Normal Form(CNF): Clause를 and로 결합한 것

 

The CNF Satisfiability Problem이란?

-> 주어진 식(CNF)을 참으로 만드는 변수들이 있는지 결정하는 문제

-> x가 주어지면 푸는 건 쉽다. 그러나 답이 되는 x를 찾는 건 어렵다.

 

 

 

 

Transformation Algorithm

 

 

 A문제에 대해 풀고 싶은데 B문제에 대한 답을 안다고 가정
-> A문제를 B문제로 변형할 수 있다면 A문제도 풀 수 있다.

 

 

 

 

Polynomial-time Many-One Reducibility

 

A->B로 변환한게 Polynomial-time  걸린다면 기호로 A ∝B (A reduces to B) 이렇게 표현

 

 

-> Theorem 1: decision problem B 가 P에 속하고, A ∝B라면

decision problem A는 P에 속한다.

 

 

 

NP-complete

 

(제대로 정의)

: B가 NP에 속하고, NP에 속하는 다른 모든 A가 A ∝B라면

B는 NP-complete이라한다.

 

-> Theorem 2: CNF-Satisfiability는 NP-complete이다.

Theorem 3: 문제 C가 NP에 속하고, NP-complete problem인 다른 B가 B ∝C라면

C는 NP-complete이다.

 

 

* NP의 상태

(⊆: 부분집합, ⊂: 진부분집합)

(A⊂B: 적어도 B의 원소 중 1개는 A에 포함되지 않는다)

1. P ⊆NP 인건 알지만 NP –P = ∅인지는 모른다.

2. NP complete problem ⊆ NP인건 안다.

-> NP complete problem⊂  NP도 맞다.

왜? 모든 질문에 대해 yes라고 대답하는 자명한 decision problem은 NP에 있지만

NP complete problem은 아니기 때문.

3. If P = NP, NP-C ⊂ P.
    If P ⊂ NP, NP-C ∩ P = ∅.

 

 

 

 

 

Polynomial-Time Turing Reducibility

:  문제 B에 대한 가상의 polynomial-time algorithm이 존재하다고 가정하여 

문제 A를 B로 변형시켜  polynomial-time으로 풀린다면

문제 A is  Polynomial-Time Turing Reducibility to 문제 B.

->

 

• A와 B가 decision problem일 필요 없다
• B가 polynomial-time에 풀리는 알고리즘은 존재하지 않는다.(가상임)

 

 

 

 

NP-Hard Problems

: NP-complete 문제인 A가 B로 튜링 되면 

B는 NP-hard라 한다.

 

 

• B는 NP에 없어도 됨.
• B는 decision problem 아니어도 됨
• 모든 NP는 튜링 하면 NP-hard가 된다
• NP-hard가 polynomial-time으로 풀 수 있다면 P=NP
• NP-complete으로 대응되는 어느 최적화 문제는 NP-hard이다.