Professor Ernesto Gomez
phone: (909) 537-5429
office:
jb337
email: ernesto@csusb.edu
office
hours: M-W 2-4 PM (or by appointment)
Announcements: The Final
Assignments
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).
Description:
"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.
Prerequisites :
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
will need.
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
Additional references:
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
Websites
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
Related stuff:
Douglas Hofstadter, "Goedel, Escher, Bach: An eternal golden
braid"
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!
EVALUATION
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