Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems

오만 You now know how to program. – you may feel like: “ Give me a problem. I will program its solution and let the computer solve it for any input of the problem. ” But do you know? – If computers can solve the problem? – If computers can solve the problem quickly enough?

Reality The Set of All Problems a set of problems that machines cannot solve. (e.g. Halting problem) a set of problems that machines can solve. in reasonable time in un- reasonable time

Tractable vs. Intractable Tractable Computation – Can usually be completed within a reasonalbe time period. Intractable Computation – Requires astounding amounts of time to complete.

Search Problem Given: three arrays, name, height, and weight Find: the names of people with a specified height and weight

Execution Time of the Search Problem t = 5.1 * * n n = 10,000  t = 초 n = 300 x 10 6  t = 153,000 초 A tractable computation!!

Sorting Problem t = 2.1 * * n * log 2 n A tractable computation!!

Tractable Computations A computation is called tractable if its execution time is given by a polynomial of n. – E.g., t = 3 * n 2 t = 4 * n 2 * log 2 n + 3 * n t = 17 * (log 2 n) 2 + n

Intractable Computations A computation is called intractable if its execution time grows faster than any polynomial of n. – E.g., t = 6 n

Permutation Problem: generate all permutations t = 4.6 * * n! An intractable computation!!

Intractability of Permutation Problem There is an algorithm for the permutation problem, but n (problem size)t (approximate) 시간 일 일 년 1751,882 년 1917,743,767 년 217,452,382,483 년 22163,952,414,630 년 (70! = 1.19 x 10 ) 100

So How Slow? n (problem size)t (approximate) 년 1751,882 년 1917,743,767 년 217,452,382,483 년 22163,952,414,630 년 Consider: - Sun will burn out in a few billion years. - Universe is about 15 billion years old. - Universe has about 10 atoms. 25

Traveling Salesman Problem Given: a set of n cities and distances among them Find: a shortest route that visits all the cities and returns to the home city

Number of Different Paths (n-1)! 2

NP Problems Problems that can be solvable in polynomial time by non-deterministic computers – non-deterministic computers = can execute one command non-deterministically from n commands Traveling salesman problem is in NP – 매번 선택할 도시들의 후보중에서 non- deterministically 선택 – 선택이 최적으로 진행되는 경우

NP-Complete Problems Traveling Salesman Problem is NP-complete. –“ NP 문제 중에서 제일 왕초이다 ” “ A problem A is NP-complete. ” 의 의미: –“ complete ” : “ 빠뜨림이 없는 ” 이라는 뜻 – 뭘 빠뜨리지 않는가? – NP 문제들을 빠뜨림없이 모두 빨리(in polynomial time) 풀어낼 수 있다, 만일 – A가 빨리(in polynomial time) 풀어진다면, A를 이용해서. One of the Greatest Unsolved Mystery in CS&E: – NP 문제이면서 P 문제는 아닌 문제가 있는가? (NP P?) – 어느 누구도 그러한 문제를 발견 못함.