What is the computational cost of automating brilliance or serendipity?(Computational complexity and P vs NP question)COS 116: 4/15/2008Sanjeev AroraCombination lockWhy is it secure?(Assume it cannot be picked)Ans: Combination has 3 numbers 0-39…thief must try 393 = 59,319 combinationsExponential running time 2n time 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 satisfiabilityDoes it 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 found “satisfying assignments” to our neural circuits for music appreciationThere are many computational problemswhere finding a solution involves “finding aneedle in a haystack”….CLIQUE ProblemIn this social network, is there a CLIQUE with 5 or more students?CLIQUE: Group of students, every pair of whom are friendsWhat is a good algorithm for detecting cliques?How does efficiency depend on network size and desired clique size?Rumor mill problemSocial network for COS 116Each node represents a studentTwo nodes connected by edge if those students are friendsJohanna starts a rumorWill it reach Kieran?Suggest an algorithmHow does running time depend on network size?Internet servers solve this problem all the time (“traceroute” in Lab 9).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 universeCan we design smarter algorithms (as for“Rumor Mill”)? Say, n2 running time.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!Traveling Salesman Problem (aka UPS Truck problem)Input: n points and all pairwise inter-point distances, and a distance kDecide: is there a path that visits all the points (“salesman tour”) whose total length is at most k?Finals schedulingInput: n students, k classes, enrollment lists, m time slots in which to schedule finalsDefine “conflict”: a student is in two classes that have finals in the same time slotDecide: if schedule with at most 100 conflicts exists?The P vs NP QuestionP: problems for which solutions can be found in polynomial time (nc where c is a fixed integer and n is “input size”). Example: Rumor MillNP: problems where a good solution can be checked in nc time. Examples: Boolean Satisfiability, Traveling Salesman, Clique, Finals SchedulingQuestion: Is P = NP? “Can we automate brilliance?”(Note: Choice of computational model ---Turing-Post, pseudocode, C++ 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 others How 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 functionGeneral 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: Factoring problemGiven a number n, find two numbers p, q (neitherof which is 1) such that n = p x q.Any suggestions how to solve it?Fact: This problem is believed to be hard.It is the basis of much of cryptography.(More next time.)Example 3: Quantum ComputationCentral 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 4: 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. (Will talk more about AI in a couple weeks)Why is P vs NP 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”).Next time: Cryptography (practical use of computational
View Full Document
Unlocking...