Complexity of ComputationWeb version of an exhibition originally held at the National Portrait Gallery, Sept. 26, 1997-Jan. 4, 1998. This site provides information on the collection of portraits by the American photographer Mathew Brady (1823?-1896) in the Gallery's collection as well as biographical and professional information on Brady. |
Contents
SuperExponential Complexity of Presburger Arithmetic | 27 |
Generalized FirstOrder Spectra and PolynomialTime Recognizable | 43 |
On kTape Versus k1Tape Real Time Computation | 75 |
An Improved Overlap Argument for OnLine Multiplication | 97 |
StringMatching and Other Products | 113 |
The Evaluation of Determinants by Expansion by Minors and the Gen | 127 |
The Complexity of Linear Approximation Algorithms | 135 |
Computational Complexity of OnePoint and MultiPoint Iteration | 149 |
| 161 | |
Common terms and phrases
a₁ A₂ Aanderaa algorithm alphabet approximation arithmetic operations Assume automata automata theory b₁ c₁ C₂ closed under complement computational complexity context-free languages context-sensitive languages COROLLARY DCSL decision problems defined denote deterministic and nondeterministic deterministic Turing machine digit efficiency encoding equivalent exists a constant finite automaton finite structures first-order formula function halts Hence input tape interval k-head k-tape Kung and Traub L₁ LBA problem Lemma length linear linearly bounded log log lower bound M₁ maps Mo(i multi-point iteration multi-tape Turing machine natural numbers NDCSL NDPTIME nondeterministic Turing machine NP-complete NP₁ on-line multiplication overlap P₁ polynomial positive integer Presburger arithmetic Project MAC proof of Theorem prove recognizable recognizable language recognized recursive regular expression regular sets result S₁ scanned sentence sequence simulation spectra spectrum steps string TALLY tape square Theorem tion upper bounds variables W₁ Z₁