What is the computational cost of automating brilliance or serendipity? (P vs NP question and related musings)Combination lockExponential running timeBoolean satisfiabilityDiscussionA ProposalRumor mill problemCLIQUE ProblemHarmonious Dorm FloorExhaustive Search/Combinatorial ExplosionTraveling Salesman Problem (aka UPS Truck problem)Finals schedulingThe P vs NP QuestionNP-complete Problems“Reduction”Dealing with NP-complete problemsComputational Complexity Theory: Study of Computationally Difficult problems.Example 1: EconomicsExample 2: Quantum ComputationExample 3: Artificial IntelligenceWhy P vs NP is a Million-dollar open problemMore than a lens: some practical uses of computational complexityWhat is the computational cost of automating brilliance or serendipity?(P vs NP question and related musings)COS 1164/18/2006Instructor: Sanjeev AroraCombination lockWhy is it secure?(Assume it cannot be picked)Ans: If the combination has 6 digits, thiefmust try 106= 1 million combinationsExponential running time2ntime to solve instances of “size” nMain fact to remember: For n =300, 2n> number of atoms in the visible universe.Increase n by 1 Æ running time doubles!Boolean satisfiability Does this formula have a satisfying assignment? What if instead we had 100 variables? 1000 variables? How long will it take to determine the assignment?(A + B + C) · (D + F + G) · (A + G + K) · (B + P + Z) · (C + U + X)DiscussionIs there an inherent difference between being creative / brilliant and being able to appreciate creativity / brilliance?What is a computational analogue of this phenomenon?A ProposalBrilliance = Ability to find “needle in a haystack”Comments??Beethoven finds “satisfying assignments” to our neural circuits for music appreciationRumor mill problem Social network for COS 116 Each node represents a student Two nodes connected by an edge iff corresponding students are friends Elaine starts a rumor Will it reach Will? Suggest an algorithm How does running time depend on network size? Internet servers solve this problem all the time (“traceroute” in Lab 8).CLIQUE Problem In COS 116 social network, is there a CLIQUE with 5 or more students? CLIQUE: Group of students, every pair of whom are friends What is a good algorithm for detecting cliques? How does efficiency depend on network size and desired clique size?Harmonious Dorm FloorGiven: Social network involving n students.Edges correspond to pairs of students who don’t get along.Decide if there is a set of k students who would make a harmonious group (everybody gets along).Just the Clique problem in disguise!Exhaustive Search/Combinatorial ExplosionNaïve algorithms for many “needle in a haystack”tasks involve checking all possible answers Æexponential running time. Ubiquitous in the computational universe Can we design smarter algorithms?Traveling Salesman Problem (aka UPS Truck problem) Input: n points and all pairwise inter-point distances, a number k Decide: is there a path that visits all the points (“salesman tour”) whose total length is at most k?Finals scheduling Input: n students, k classes, enrollment list for each class, m time slots in which to schedule finals Define “conflict”: a student who is in two classes that have finals in the same time slot Decide: Is there a finals schedule with at most C conflicts?The P vs NP Question P: problems for which solutions can be found in polynomial time (ncwhere c is a fixed integer and n is “input size”). Example: Rumor Mill NP: problems where a good solution can be checked in nctime. Example: Boolean Satisfiability, Traveling Salesman, Clique Question: Is P = NP?“Can we automate brilliance?”?(Aside: Choice of computational model ---Turing machine, pseudocode, etc.--- irrelevant.)NP-complete ProblemsProblems in NP that are “the hardest” If they are in P then so is every NP problem.Examples: Boolean Satisfiability, Traveling Salesman, Clique, Finals Scheduling, 1000s of othersHow could we possibly prove these problems are “the hardest”?“Reduction”“If you give me a place to stand, I will move the earth.”– Archimedes (~ 250BC)“If you give me a polynomial-time algorithm for Boolean Satisfiability, I will give you a polynomial-time algorithm for every NP problem.” --- Cook, Levin (1971)“Every NP problem is a satisfiabilityproblem in disguise.”Dealing with NP-complete problems1. Heuristics (algorithms that produce reasonable solutions in practice) 2. Approximation algorithms (compute provably near-optimal solutions)Computational Complexity Theory: Study of Computationally Difficult problems. Study matter → look at mass, charge, etc. Study processes → look at computational difficultyA new lens on the world?Example 1: EconomicsGeneral equilibrium theory: Input: n agents, each has some initial endowment (goods, money, etc.) and preference function General equilibrium: system of prices such that for every good, demand = supply. Equilibrium exists [Arrow-Debreu, 1954]. Economists assume markets find it (“invisible hand”) But, no known efficient algorithm to compute it. How does the market compute it?Example 2: Quantum Computation Central tenet of quantum mechanics: when a particle goes from A to B, it takes all possible paths all at the same time [Shor’97] Can use quantum behavior to efficiently factor integers (and break cryptosystems!) Can quantum computers be built, or is quantum mechanics not a correct description of the world?ABPeter ShorExample 3: Artificial IntelligenceWhat is computational complexity oflanguage recognition?Chess playing?Etc. etc.Potential way to show the brain is not a computer:Show it routinely solves some problem that provably takes exponential time on computers.Why P vs NP is a Million-dollar open problem If P = NP then Brilliance becomes routine (best schedule, best route, best design, best math proof, etc…) If P ≠ NP then we know something new and fundamental not just about computers but about the world (akin to “Nothing travels faster than light”).More than a lens: some practical uses of computational complexityExample 1: CAPTCHAsExample 2 (next time):
View Full Document
Unlocking...