Search
Now showing items 1-5 of 5
Super-exponential Complexity of Presburger Arithmetic
(1974-02)
Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first order theory of the real numbers under ...
An Improved Overlap Argument for On-line Multiplication
(1974-01)
A lower bound of cN1ogN is proved for the mean time complexity of an on-line multitape Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines the corresponding bound ...
String-matching and Other Products
(1974-01)
The string-matching problem considered here is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is an algorithm due to Morris, ...
Fast On-line Integer Multiplication
(1974-05)
A Turing machine multiplies binary integers on-line if it receives its inputs low-order digits first and produces the jth digit of the product before reading in the (j+l)st digits of the two inputs. We present a general ...