📄 http:^^www.cs.rutgers.edu^~allender^538^
字号:
Date: Tue, 26 Nov 1996 18:52:54 GMT
Server: NCSA/1.5.2
Last-modified: Tue, 23 Jan 1996 16:05:54 GMT
Content-type: text/html
Content-length: 3466
<!doctype html public "-//W3O//DTD W3 HTML 2.0//EN"><HTML><HEAD><TITLE>Syllabus for 198:538</TITLE><BODY><H1>198:538: Complexity of Computation </H1><b>Meeting times and locations:</b> Mondays and Wednesdays, 2:50--4:10 SEC 203.<br>Index number for registration: 72693<H1> Professor <!WA0><a href=http://www.cs.rutgers.edu/~allender>Eric Allender</a> </H1><HR><address> Phone: (908) 445-3629<br> FAX: (908) 445-0537<br> <p>Email: allender@cs.rutgers.edu<P>Office: Hill 442<br>Click here for current <!WA1><a href=http://www.cs.rutgers.edu/~allender/hours>Office Hours</a>.</address><HR><strong>Text:</strong> Christos Papadimitriou: <i>Computational Complexity</i>.<br>Various papers on recent results will supplement the text.<HR><strong> ROUGH COURSE OUTLINE</strong>The actual list of topics may vary slightly from the list that followsbelow, depending on the interests of the class. For instance, it wouldbe quite possible to include more material about the relationship betweenfinite model theory and complexity theory, if there is sufficient interest.<ul><li>This course covers the field ofcomputational complexity theory, beginning with the fundamental theoremsthat delimit what one can expect of such a theory. We will also studythe diagonalization techniques that continue to be among the most powerfultools in complexity theory. <ul> <li> Gap Theorem, Hierarchy Theorems <li> Blum Speed-Up Theorem, Levin's Lower Bound Theorem </ul><li>The notions that have the most practical importance in classifying the complexity of problems are <b>complexity classes</b> and <b>reducibility</b> among problems. Many important complexity classesare characterized most simply in terms of variants of <b>Nondeterministiccomputation</b>. <ul> <li> Immerman-Szelepcsenyi Theorem <li> Nondeterministic Time Hierarchy Theorem <li> Feasible Computation; Reducibility, Completeness </ul><li><b>Alternation</b>, a generalization of nondeterminism, is veryuseful in relating time and space complexity, and it also modelsparallel computation and circuit complexity. <ul> <li>Alternating Turing Machines <li>Basic relations to Dtime and Dspace <li>Circuit Complexity, Parallel Computation <li>The Polynomial Hierarchy <li>Branching Programs; Barrington's Theorem </ul><li>Probabilistic Computation and Circuit Complexity <ul> <li>Presentation of problems requiring large circuits <li>NP has small circuits implies PH collapses; related results <li>Probabilistic Complexity Classes; Basic Inclusions and Closure Properties <li>Deterministic circuits simulate probabilistic computation. <li>BPP is in PH <li>Toda's Theorem: PH is reducible to PP <li>Closure properties of PP; connections to threshold circuits. </ul><li>Relativization Results; Oracles relative to which P=NP and oraclesrelative to which P is not equal to NP, and related results.<li>Interactive Proofs <ul> <li>Collapse of the AM Hierarchy <li>Elimination of Private Coins <li>IP=PSPACE <li>NEXPTIME = 2-prover interactive proofs. <li>Non-Relativizing Proof Techniques </ul><b>Prerequisites:</b> 198:452, 198:509, and 198:513, <b>OR</b> familiarity with the basic notions of data structures and algorithms, and common models of computation (e.g., Turing machines, finite automata, etc.)<p><b>Expected Work:</b> Bi-weekly <!WA2><a href=http://www.cs.rutgers.edu/~allender/538/homework>homework</a> assignments.</BODY>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -