Intractable Problem

Intractable은 아주 다루기 힘든이란 뜻으로 Intractable Problem이란 말 그대로 풀기 힘든 문제라는 뜻이다.

• 문제 P에 대한 효율적인 알고리즘은 발견 되지 않았지만, 그 문제가 많은 시간을 필요로 한다는 것을 증명한 사람도 없었다.
• 문제 P에 대한 exponential time algorithm 이 있지만 아무도 polynomial time algorithm을 찾을 수 없었고, P에 대한 exponential time algorithm이 존재하지 않음을 증명 할 수 있다.
• exponential time alogrithm 이 발견된 문제 중 가장 어려운 문제 그룹인 NP-Complete이 있는데 이 그룹의 문제에 대한 Polynomial time algorithm을 발견하면 exponential time algorithm이 존재하는 모든 난해한 문제에 대한 polynomial time algorithm이 존재한다는 것을 증명한다.

일반적으로 Computer Science에서 문제를 polynomial time algorithm으로 푸는게 불가능 할 경우 이를 intractable하다고 부른다

---

NP-Complete 문제들

Example: Hamiltonian Path(Cycle) Problem (HP/HC)

Hamiltonian path 란?

   => 각 정점을 정확히 한번 방문하는 그래프 내에서의 path를 의미한다.

Hamiltonian cycle 이란?

   => 각 정점을 정확히 한번 방문하며 또한 시작 정점으로 되돌아오는 경우를 의미한다.

Problem : Hamiltonian path(cycle)이 주어진 그래프에 존재할지에 대한 결정 

Fact : 둘 다 NP-Complete 문제이다. 

 

Example : Longest Path Problem (LP)

Simple path는 어떠한 정점들을 반복하지 않은 path를 의미한다.

Problem : Find a simple path of maximum length in a given graph G = (V, E).

Fact : This problem is NP-Complete.

 

Example : Bin Packing Problem (BP)

Problem : Suppose a CD-ROM can store up to 720MBytes of data. 

You have a sequence of n files of sizes s1 , s2 , …, sn Mbytes, to dump into backup CDs. 

What is the minimum number of necessary CDs to store all the files?

Fact : NP-Complete 문제이다.