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 (24)

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 ⋮ Quantum circuits for high-degree and half-multiplication for post-quantum analysis ⋮ Survey number theoretic transform algorithm over a polynomial ring and its application ⋮ Implementing lattice-based PQC on resource-constrained processors: a case study for Kyber/Saber's polynomial multiplication on ARM Cortex-M0/M0+ ⋮ Algorithmic views of vectorized polynomial multipliers -- NTRU ⋮ Exploring the advantages and challenges of Fermat NTT in FHE acceleration ⋮ Space-efficient and noise-robust quantum factoring ⋮ 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

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On the Minimum Computation Time of Functions