📄 http:^^cs-www.bu.edu^faculty^lnd^ftp^toc^
字号:
Date: Tue, 14 Jan 1997 23:00:17 GMTServer: NCSA/1.5Content-type: text/html <html><head><BASE HREF="http://www.cs.bu.edu/faculty/lnd/ftp/toc/"><title> L. Levin. Theory of Computation. </title></head><body text="#000000" bgcolor="#ffffd0" link="#0080ff" vlink="#c00090" alink="#00cc80"> <H1><!WA0><a href="http://www.cs.bu.edu/faculty/lnd/"> Leonid Levin. </a> Fundamentals of Computing. </H1> <b> The <!WA1><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/z.dvi">DVI</a> file; The <!WA2><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/z.ps">Postscript</a> file; The BUGGY <!WA3><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/z/z.html"> HTML </a> files.</b> <P><b> The LaTeX sources: <!WA4><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/a-abst"> Foreword. </a></b><OL> <LI><b> Models of Computations; Polynomial Time and Church's Thesis. </b><OL> <LI><b><!WA5><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/b-base"> Deterministic Computation. </a></b> <LI><b><!WA6><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/c-cell"> Rigid Models. </a></b> <LI><b><!WA7><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/d-point"> Pointer Machines. </a></b> <LI><b><!WA8><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/e-equiv"> Simulation. </a></b></OL> <LI><b> Universal Algorithm; Diagonal Results. </b><OL> <LI><b><!WA9><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/f-univ"> Universal Turing Machine. </a></b> <LI><b><!WA10><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/g-godel"> Uncomputability; Godel Theorem. </a></b> <LI><b><!WA11><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/h-hard"> Intractability; Compression and Speed-up Theorems. </a></b></OL> <LI><b> Games; Alternation; Exhaustive Search; Time v. Space. </b><OL> <LI><b><!WA12><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/i-games"> How to Win. </a></b> <LI><b><!WA13><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/j-haltg"> Exponentially Hard Games. </a></b> <LI><b><!WA14><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/k-chess"> Reductions; Non-Deterministic and Alternating TM; Time/Space. </a></b> <LI><b><!WA15><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/l-lean"> Fast and Lean Computations. </a></b></OL> <LI><b> Nondeterminism; Inverting Functions; Reductions. </b><OL> <LI><b><!WA16><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/m-inv"> Example of a Narrow Computation: Inverting a Function. </a></b> <LI><b><!WA17><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/n-npcom"> Complexity of NP Problems. </a></b> <LI><b><!WA18><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/o-tile"> An NP-Complete Problem: Tiling. </a></b></OL> <LI><b> Randomness in Computing. </b><OL> <LI><b><!WA19><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/p-prime"> A Monte-Carlo Primality Tester. </a></b> <LI><b><!WA20><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/q-prob"> Randomized Algorithms and Random Inputs. </a></b> <LI><b><!WA21><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/r-rand"> Randomness and Complexity. </a></b> <LI><b><!WA22><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/s-pseud"> Pseudo-randomness. </a></b> <LI><b><!WA23><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/t-crypt"> Cryptography. </a></b></OL></OL> <b><!WA24><a href="http://www.cs.bu.edu/faculty/lnd/ftp/toc/u-ref"> References. </a></b> <P> See also *.dvi files with some of my <!WA25><a href="http://www.cs.bu.edu/faculty/lnd/ftp/papers/">papers</a>. </body></html> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -