Lower Bounds in Algorithm Analysis PDF

**[Lower Bounds]** **Definition:** - An estimate on a minimum amount of work needed to solve a given problem. - An exact count. - An efficiency class (Ω). - Tight lower bound: There exists an algorithm with the same efficiency as the lower bound. **Examples:** Number of compari...

**[Lower Bounds]** **Definition:** - An estimate on a minimum amount of work needed to solve a given problem. - An exact count. - An efficiency class (Ω). - Tight lower bound: There exists an algorithm with the same efficiency as the lower bound. **Examples:** Number of comparisons needed to - find the largest element in a set of n numbers. - sort an array of size n. - searching in a sorted array. - multiply two n-by-n matrices. **Methods for Establishing Lower Bounds** - Trivial lower bounds. - Information-theoretic arguments (decision trees). - Adversary arguments. - Problem reduction. ### [Lower Bounds by Problem Reduction] +-----------------------------------+-----------------------------------+ | **Reduction** | **Lower Bounds by Problem | | | Reduction** | +===================================+===================================+ | - Min-heap reduces to max heap. | - A \[Ω(f)\] reduces to B | | | \[Ω(?)\]. | | - Minimum reduces to sort. | | | | - B \[Ω(?)\] reduces to A | | - Element uniqueness for pairs | \[Ω(f)\]. | | reduces to closest pair. | | | | - \[Assume the reduction | | | itself is fast (i.e., | | | O(f))\]. | | | | | | - A = \[Ω(?)\], resulting | | | in nothing. | +-----------------------------------+-----------------------------------+ **To show lower bounds:** Reduce problem with known lower bound to problem with an unknown lower bound. **Idea:** If problem P is at least as hard as problem Q, then a - lower bound for Q is also a lower bound for P. - find problem Q with a known lower bound that can be reduced to problem P in question. **Example:** - P is finding MST for n points in the Cartesian plane. - Q is the element uniqueness problem (known to be in Ω(n log n)). - Result: P (MST) reduces to Q (element uniqueness), both are Ω(n log n). **Reduce Element Uniqueness to MST:** - Input: Unique set ( S = {x~1~, x~2~, x~n~} ). - Create pairs: ( P = {( x~1~, 0), (x~2~, 0), (x~n~, 0)} ). - Find MST: ( T = MST(P) ). - Compute: ( D = min\_length ). - Return ( D = 0 ). - Thus, MST is Ω(n log n)! **[Trivial Lower Bounds:]** Based on counting no. of items must be processed in input and generated as output. +-----------------------------------+-----------------------------------+ | **Examples** | **Conclusions** | +===================================+===================================+ | - Finding the max element. | - May or may not be useful. | | | | | - Polynomial evaluation. | - Be careful in deciding how | | | many elements must be | | - Sorting. | processed (min-max). | | | | | - Element uniqueness. | | | | | | - Hamiltonian circuit | | | existence. | | +-----------------------------------+-----------------------------------+ ### [Decision Trees] **Definition:** Model algorithms that use comparisons: - Internal nodes represent comparisons. - Leaves represent outcomes. - How many orderings of 2 elements? Of 3? Of n? - Tree for 3-element insertion sort \[insert b in a, then c into ab\]. **Decision Trees and Sorting Algorithms:** - Any comparison-based sorting algorithm can be represented by a decision tree. - Number of leaves (outcomes) ≥ n! - Height of binary tree with n! leaves ≥ ⌈log₂n!⌉. - Minimum no. of comparisons in the worst case ≥ ⌈log₂n!⌉ for any comparison-based sorting algorithm. - ⌈log₂3!⌉ = ⌈log₂6⌉ = 3. - ⌈log₂n!⌉ ≈ n log₂n, for large n. - This lower bound is tight (mergesort). ### P, NP, and NP-Complete +-----------------------------------+-----------------------------------+ | **Classifying Problems** | **Problem Classes** | +===================================+===================================+ | - Tractable and non-tractable | - **P**: solvable in polynomial | | | time (O(p(n))). | | - Optimization | | | | - **NP**: verifiable in | | - Decision Problems | polynomial time. | | | | | | - **NP-Complete**: The | | | hardest - reducible to | | | polynomial time. | +-----------------------------------+-----------------------------------+ **Classifying Problem Complexity:** Is the problem tractable, a polynomial-time (O(p(n))) algorithm that solves it? +-----------------------------------------------------------------------+ | **Possible answers** | +=======================================================================+ | - **Yes: الامثله زياده** | | | | - searching, | | | | - element uniqueness, | | | | - graph connectivity | | | | - **No: Because it's been proved that** | | | | - **no algorithm exists at all** Turing's halting problem | | | | - **any algorithm takes exponential time**. | | | | - **Unknown**. | +-----------------------------------------------------------------------+ **Problem Types:** Decision problems are more convenient for formal investigation of their complexity. **Problem Types** **Definition** **Traveling Salesman Problem** ------------------- ------------------------------------------------------------------- ------------------------------------------- **Optimization** Find a solution that maximizes or minimizes an objective function Find Hamiltonian cycle of minimum length. **Decision** Answer yes/no to a question. Find Hamiltonian cycle of length ≤ m. **[Class P: ]** +-----------------------------------+-----------------------------------+ | **Definition** | **Example** | +===================================+===================================+ | - Class of decision problems | - Searching | | | | | - solvable in O(p(n)) time. | - Element uniqueness | | | | | - *p*(*n*)=polynomial of | - Graph connectivity | | problem's | | | | - Graph acyclicity | | - input size= *n* | | | | - Primality testing | +-----------------------------------+-----------------------------------+ ### [Class NP] ### Definition - **NP (Nondeterministic Polynomial)**: - Class of decision problems whose solutions can be verified in polynomial time. - solvable by a *nondeterministic* *polynomial algorithm* - it solves the problem if it will generate and verify a solution on one of its tries - led to development of the rich theory called "computational complexity" **Algorithm:** abstract two-stage procedure that 1. Generates a random string that may solve the problem. 2. Checks if the solution is correct in polynomial time. **Example: CNF Satisfiability** conjunctive normal form - Problem: Is a Boolean expression in CNF satisfiable? are there values of its variables that makes it true? - Algorithm: - Guess truth assignment. - Substitute the values into the CNF formula to see if it evaluates to true. (Checking phase: O(*n*)) **Problems in NP:** - Hamiltonian circuit existence - Partition problem; possible to partition set of *n* integers into two disjoint subsets with the same sum? - Decision versions of TSP, knapsack problem, graph coloring Few exceptions include: MST, shortest paths **Relationship:** - All problems in P are in NP. - Question: Is P = NP or is P ⊂ NP? - Answer unknown. Current approach: focus on hardest NP problems ### NP-Complete: The Hardest NP Problems - **NP-Complete**: A decision problem D in NP is NP-complete if: - D is in NP. - Every problem in NP is polynomial-time reducible to D. **First NP-Complete Problem:** **Cook's Theorem (1971)**: CNF-sat is NP-complete. ### Proving [ ] Other Problems are NP-Complete - Prove by polynomial-time reductions from a known NP-complete problem. - Pay attention to the direction of the reductions - Examples: TSP, knapsack, partition, graph-coloring. ### P = NP? Dilemma Revisited - If P = NP, every problem in (NP and *NP-*complete) could be solved in polynomial time. - If a polynomial-time algorithm for one NP-complete problem is found, every problem in NP can be solved in polynomial time. - Most researchers believe P ≠ NP (P is a proper subset of NP). ### [Summary] **P**: Class of decision problems that can be solved in polynomial time. **NP**: Class of decision problems where randomly guessed solution can be verified in polynomial time. **NP-Complete Problems**: Hamiltonian circuit problem, to which all other NP problems are reducible in polynomial time. **S. Cook\'s Contribution**: The first proof of a problem\'s NP-completeness, specifically for the CNF-satisfiability problem. **P vs NP**: Whether P equals NP or if P is a proper subset of NP is an unresolved issue in theoretical computer science. Discovering a polynomial-time algorithm for any NP-complete problem would imply P = NP. **Reduction for Lower Bound**: Establishes a lower bound by reducing a problem with a known lower bound to the problem in question. **Complexity Theory**: Classifies problems according to their computational complexity, distinguishing between tractable problems (solvable in polynomial time) and intractable problems (not solvable in polynomial time). **Halting Problem**: An example of an undecidable decision problem that cannot be solved by any algorithm.