Professor Ernesto Gomez
phone: (909) 537-5429
office hours: M-W 2-4 PM (or by appointment)
Announcements: The Final
Searching for papers in the Pfau Library: (you must be either on the campus network or use a VPN to access this from outside - see library web pages for how to do this).
From main Pfau Library page (http://www.lib.csusb.edu) select "Articles or Journals". Use the "By Subject" link to select "Computer Science". Use the ACM, IEEE or Springer links to search (ACM will find articles in IEEE or Springer and take you to them also).
"Computational complexity theory is at the core of
theoretical computer science research" - Avi Widgerson,
Professor, Institute for Advanced Study, Princeton
Computational models - do they affect complexity? Turing machines, cellular automata, quantum computers, others?
Review of polynomial complexity classes, NP, Pspace, the P vs NP problem.
Circuit complexity - a very different view of complexity, giving insight into parallelism and hardware limits. Appears to be equivalent to Turing machines, but allows different insight into problems.
Randomized computation and interactive proofs - randomness does not appear to affect the major complexity classes (NP with randomness is still NP) - but randomized computation can be not just faster than deterministic, but actually a lower order of complexity.
Quantum computation and complexity - we can't do this yet, but we are starting to apply quantum encryption. Expect this will be increasinly relevant in the near future. This is the only computational model that might break the hierarchy - it is possible that quantum computers will be able to solve NP problems in P time, for instance - this is still controversial, there are strong arguments both pro and con.
Other topics may be selected by the class.
Notice that we will be sudying different computational models (circuit, quantum) and the effects of randomness (true randomness requires extra hardware - does this matter, or can we work with pseudo-random generators in software?). A question to focus your reading - does the hardware matter? Chapter one in the text says it does not, based on the concept that standard computational models are within a polynomial factor of each other, so problems remain in the same complexity class. However...
-- Quantum computing may allow us to solve problems that are exponential on a standard computer in polynomial time. (Deutsch thinks yes - hardware matters, Aaronson thinks no - see refs below).
-- Do Turing Machines set the limits of what can be computed? Hofstadter (see below) and pretty much everybody else - thinks yes, all models of general computation are equally powerful. Penrose thinks no - thinks new physics in the brain allows computation beyond T.M.. Penrose is in a timy minority here, but he is one of the greatest math and physics geniuses working now, so his opinion carries a lot of weight.
As you sudy this material, think of where you stand on the "hardware matters" issue.
You should have some knowledge of Turing machines and basic
complexity classes like P and NP - however since this is the first
time we teach the material of this course, we expect to provide
substantial review of these topics. Ideally you should have taken
the old 546 or 646, or the new 600, (or some reasonably equivalent
theory of computation course). An undergraduate algorithms course
should also give you most of the basic knowledge of complexity you
We have just revamped the CS 500/600/546/646 course sequence; those students who entered the program while the previous sequence still applied, particularly if they have already taken some of these courses, will probably not have the official prerequisites. You should be able to register with consent of the instructor, check at the Computer Science Department office.
Text: Computational Complexity Theory - A modern Approach, sanjeev Arora and Boaz Barak, Cambridge University Press 2009
Michael Sipser, "Introduction to the Theory of Computation", Second Edition, Thomson
John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley
John C. Martin, "Introduction to Languages and the Theory of Computation - Second Edition", McGraw-Hill
Raymond Greenlaw, H.James Hoover, Walter L. Ruzzo; "Limits to Parallel Computation", Oxford University Press
Herken (ed.); "The Universal Turing Machine - A Half-Century Survey", Springer-Verlag (on reserve in the library)
Marvin L. Minsky, "Computation: Finite and Infinite Machines", Prentice Hall Series in Automatic Computation
"Godel's Proof - (Revised Edition)", Ernest Nagel and James R. Newman, edited by Douglas Hofstadter,New York University Press 2001
C. J. Chaitin One of the foremost theorists on complexity and algorithms
"David Deutsch A principal exponent of quantum computing, proved that a quantum Turing Machine is possible
Scott Aaronson A complexity theorist and quantum computing skeptic, and an extremely interesting writer - his article "NP-complete Problems and Physical Reality" - see suvey papers - which includes a serious look at what you could compute if you had time travel, and other less likely speculations - is not to be missed!!
The Complexity Zoo
Douglas Hofstadter, "Goedel, Escher, Bach: An eternal golden
Fascinating book about Turing machines, artificial intelligence, music, Escher's drawings, history - won the Pulitzer prize.
Roger Penrose, "The Emperor's New Mind"
Argues that digital computers and Turing machines are not the most general computational device - points out holes in our present understanding of quantum physics that maybe could lead to computation beyond Turing machines, and could be what happens in the brain. Very readable - and controversial!
You will be asked to solve problems in complexity and turn in
your results. Most of these will involve proving something. Problems
should be turned in the week after they are assigned, but this is a
recommendation only. Late work will be accepted until the last class
day of the Winter term.
You will select a paper from one of the links of this page or one of the references from the text, and present it in class, on the last week of class.
ALL WORK EXCEPT THE FINAL MUST BE TURNED IN BEFORE FINALS WEEK. Please come talk to me if this is a problem
Grades are computed as follows:
Assigned problems: 40%
Report presentations: 20%
Final (takehome): 40%
A>92; A->=90; B+>88; B>82; B->=80; C+>78; C>82; C->=70; D+>68; D>62; D->=60; F>=0