On the Minimum Computation Time of Functions

DOI10.2307/1995359zbMath0188.33402OpenAlexW4235199656MaRDI QIDQ5582354

Stål Aanderaa, Stephen A. Cook

Publication date: 1969

Full work available at URL: https://doi.org/10.2307/1995359

zbMATH Keywords

languages, automata, networks

Related Items

Tensors in computations, Squeezing Feasibility, Optimal dynamic embedding of X-trees into arrays, Integer multiplication in time \(O(n\log n)\), When NTT meets Karatsuba: preprocess-then-NTT technique revisited, Indirect addressing and the time relationships of some models of sequential computation, Kolmogoroff algorithms are stronger than Turing machines, An information-theoretic approach to time bounds for on-line computation, On the universality of peptide computing, Derivation and Analysis of Fast Bilinear Algorithms for Convolution, Linear speed-up does not hold on Turing machines with tree storages, Real-time recognition of substring repetition and reversal, On the sequential nature of functions, Number theoretic transform: generalization, optimization, concrete analysis and applications, Fast multiplication of large numbers, Fast on-line integer multiplication, Complexity lower bounds for machine computing models, Fast NEON-based multiplication for lattice-based NIST post-quantum cryptography finalists

Cites Work

• Real time computation
• Multiplikation großer Zahlen
• On the Computational Complexity of Algorithms
• The Theory of Automata, a Survey
• Boolean Memories
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• On the Time Required to Perform Multiplication
• One-tape, off-line Turing machine computations
• Computability of Recursive Functions
• Unnamed Item
• Unnamed Item