Lecture Notes 27 Complexity Theory 1 Introduction to Complexity Theory Read K & S Chapter 6. Most computational problems you will face your life are solvable (decidable). We have yet to address whether a problem is “easy” or “hard”. Complexity theory tries to answer this question. Recall that a computational problem can be recast as a language recognition problem. Some “easy” problems: § Pattern matching § Parsing § Database operations (select, join, etc.) § Sorting Some “hard” problems: § Traveling salesman problem § Boolean satisfiability § Knapsack problem § Optimal flight scheduling “Hard” problems usually involve the examination of a large search space. Big-O Notation § Gives a quick-and-dirty measure of function size § Used for time and space metrics A function f(n) is O(g(n)) whenever there exists a constant c, such that |f(n)| ≤ c⋅|g(n)| for all n ≥ 0. (We are usually most interested in the “smallest” and “simplest” function, g.) Examples: 2n3 + 3n2⋅log(n) + 75n2 + 7n + 2000 is O(n3) 75⋅2n + 200n5 + 10000 is O(2n) A function f(n) is polynomial if f(n) is O(p(n)) for some polynomial function p. If a function f(n) is not polynomial, it is considered to be exponential, whether or not it is O of some exponential function (e.g. n log n). In the above two examples, the first is polynomial and the second is exponential. Comparison of Time Complexities Speed of various time complexities for different values of n, taken to be a measure of problem size. (Assumes 1 step per microsecond.) f(n)\n 10 20 30 40 50 60 n .00001 sec. .00002 sec. .00003 sec. .00004 sec. .00005 sec. .00006 sec. n2 .0001 sec. .0004 sec. .0009 sec. .0016 sec. .0025 sec. .0036 sec. n3 .001 sec. .008 sec. .027 sec. .064 sec. .125 sec. .216 sec. n5 .1 sec. 3.2 sec. 24.3 sec. 1.7 min. 5.2 min. 13.0 min. 2n .001 sec. 1.0 sec. 17.9 min. 12.7 days 35.7 yr. 366 cent. 3n .059 sec. 58 min. 6.5 yr. 3855 cent. 2x108 cent. 1.3x1013 cent. Faster computers don’t really help. Even taking into account Moore’s Law, algorithms with exponential time complexity are considered intractable. ∴Polynomial time complexities are strongly desired.Lecture Notes 27 Complexity Theory 2 Polynomial Land If f1(n) and f2(n) are polynomials, then so are: § f1(n) + f2(n) § f1(n) ⋅ f2(n) § f1(f2(n)) This means that we can sequence and compose polynomial-time algorithms with the resulting algorithms remaining polynomial-time. Computational Model For formally describing the time (and space) complexities of algorithms, we will use our old friend, the deciding TM (decision procedure). There are two parts: § The problem to be solved must be translated into an equivalent language recognition problem. § A TM to solve the language recognition problem takes an encoded instance of the problem (of size n symbols) as input and decides the instance in at most TM(n) steps. We will classify the time complexity of an algorithm (TM) to solve it by its big-O bound on TM(n). We are most interested in polynomial time complexity algorithms for various types of problems. Encoding a Problem Traveling Salesman Problem: Given a set of cities and the distances between them, what is the minimum distance tour a salesman can make that covers all cities and returns him to his starting city? Stated as a decision question over graphs: Given a graph G = (V, E), a positive distance function for each edge d: E→N+, and a bound B, is there a circuit that covers all V where ΣΣΣΣd(e) ≤ B? (Here a minimization problem was turned into a bound problem.) A possible encoding the problem: § Give |V| as an integer. § Give B as an integer. § Enumerate all (v1, v2, d) as a list of triplets of integers (this gives both E and d). § All integers are expressed as Boolean numbers. § Separate these entries with commas. Note that the sizes of most “reasonable” problem encodings are polynomially related. What about Turing Machine Extensions? Most TM extensions are can be simulated by a standard TM in a time polynomially related to the time of the extended machine. § k-tape TM can be simulated in O(T2(n)) § Random Access Machine can be simulated in O(T3(n)) (Real programming languages can be polynomially related to the RAM.) BUT… The nondeterminism TM extension is different. A nondeterministic TM can be simulated by a standard TM in O(2p(n)) for some polynomial p(n). Some faster simulation method might be possible, but we don’t know it. Recall that a nondeterministic TM can use a “guess and test” approach, which is computationally efficient at the expense of many parallel instances.Lecture Notes 27 Complexity Theory 3 The Class P P = { L : there is a polynomial-time deterministic TM, M that decides L } Roughly speaking, P is the class of problems that can be solved by deterministic algorithms in a time that is polynomially related to the size of the respective problem instance. The way the problem is encoded or the computational abilities of the machine carrying out the algorithm are not very important. Example: Given an integer n, is there a positive integer m, such that n = 4m? Problems in P are considered tractable or “easy”. The Class NP NP = { L: there is a polynomial time nondeterministic TM, M that decides L } Roughly speaking, NP is the class of problems that can be solved by nondeterministic algorithms in a time that is polynomially related to the size of the respective problem instance. Many problems in NP are considered “intractable” or “hard”. Examples: § Traveling salesman problem: Given a graph G = (V, E), a positive distance function for each edge d: E→N+, and a bound B, is there a circuit that covers all V where ΣΣΣΣd(e) ≤ B? § Subgraph isomorphism problem: Given two graphs G1 and G2, does G1 contain a subgraph isomorphic to G2? The Relationship of P and NP We’re considering only solvable (decidable) problems. Clearly P ⊆ NP. P is closed under complement. NP probably isn’t closed under complement. Why? Whether P = NP is considered computer science’s greatest unsolved problem. RecursiveNPPLecture Notes 27 Complexity Theory 4 Why NP is so Interesting § To date, nearly all decidable problems with polynomial bounds on the size of the solution are in this class. § Most NP problems have simple
View Full Document
Unlocking...