📄 http:^^www.cs.uidaho.edu^~foster^596f94^
字号:
Date: Tue, 26 Nov 1996 19:03:50 GMTServer: NCSA/1.4.1Content-type: text/htmlLast-modified: Wed, 31 Aug 1994 15:43:28 GMTContent-length: 3380<HEAD><TITLE>CS 596 Computational Complexity Theory Home Page</TITLE></HEAD><BODY><H1>CS 596: Computational Complexity Theory</H1><P> <P><P>Computational complexity theory groups problems into classes according tohow much of particular computational resources their solutions require.Familiar examples are P and NP, which are classes of problems solvablewith at most polynomial time with and without nondeterminism. <P>We will investigate what is known about common complexity classes whichcapture such ideas as feasibility, randomized algorithms, booleancircuits, parallel computation, and interactive proofs.Along the way, we will learn some of the major recent results in thisarea---some of which were even reported in the New York Times! <P>This page contains<UL><LI> <!WA0><A HREF="#info">General information</A><LI> <!WA1><A HREF="#newsgroups">Relevant newsgroups</A><LI> <!WA2><A HREF="#stuff">Miscellaneous interesting stuff</A></UL>Please feel free to put any suggestions or comments you might have in the<!WA3><A HREF="http://www.cs.uidaho.edu/~foster/mail.html">suggestion box.<hr><H2><A NAME="info">General Information</A></H2><uL> <li> Instructor: <!WA4><A HREF="http://www.cs.uidaho.edu/~foster">James A. Foster</A><MENU><LI> Office: JEB B24<LI> Phone: 885-7062<LI> Office Hours: MF 4:30-5:20, MW 2:00-3:20<LI> Email: <tt> foster@cs.uidaho.edu</tt><LI> Prerequisites: CS 490/Ma 485 and CS 495/Math 405 (or consent of the instructor)<LI> Texts: <ul><li>Balcazar, Diaz, Gabarro, <i>Structural Complexity I</I>, Springer-Verlag, 1988.<li>(Recommended) Balcazar, Diaz, Gabarro, <i>Structural Complexity II</I>, Springer-Verlag, 1990.</ul></MENU><LI> Objectives<UL><LI> To understand the approach toward classifying computational problems taken by structural complexity: define a class of problems according to computational resources required to solve them and investigate the relationships between these classes.<LI> To understand the proof techniques used to characterize the inherent complexity of problems in this way.<LI> To be familiar with significant recent results in computational complexity theory.<LI> To gain experience presenting results of a theoretical nature.<LI> Activities</UL><LI> Activities<UL><LI> Read the text and work appropriate exercises.Note: there will be no graded homework assignments, but students are<B>strongly advised</B> to work through exercises at the end of the chapters in the text book.<LI> Take mid term examination.<LI> Give an <!WA5><A HREF="http://www.cs.uidaho.edu/~foster/596f94/present.html">oral presentation</A> of a significant result or paper.</UL><LI> Grading:Final grades will be determined with approximately equal weights on the midterm and the presentation. Consideration will be given to class participation for on campus students.<LI> Syllabus: Press <!WA6><A HREF="http://www.cs.uidaho.edu/~foster/596f94/syllabus.ps">here</A> for the syllabus</UL><hr><h2><A NAME="newsgroups">Relevant Newsgroups</A></h2><ul><li><!WA7><a href="news:uidaho.cs.theory">uidaho.cs.theory</a><li><!WA8><a href="news:comp.theory">comp.theory</a><li><!WA9><a href="news:sci.logic">sci.logic</a></ul><hr><H2><A NAME="stuff">Other Stuff of Interest</A></H2> <P>Check out <EM>FLAP</EM>, which is in <CODE>/usr/public/bin</CODE>. This is an animation program forfinite automata. </BODY><P><ADDRESS><I>foster@cs.uidaho.edu</I></ADDRESS>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -