On the Computational Complexity of Algorithms

Cites work

Classes of Predictably Computable Functions
scientific article; zbMATH DE number 3131080 (Why is no real title available?)
scientific article; zbMATH DE number 3201659 (Why is no real title available?)
scientific article; zbMATH DE number 3251431 (Why is no real title available?)
On certain formal properties of grammars
Real time computation

Cited in

(only showing first 100 items - show all)

On small, reduced, and fast universal accepting networks of splicing processors
On the structure of one-tape nondeterministic Turing machine time hierarchy
Tape versus queue and stacks: The lower bounds
Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
A note on the best-case complexity
Completeness proofs for propositional logic with polynomial-time connectives
Indirect addressing and the time relationships of some models of sequential computation
On time versus space. II
Complexity of algorithms and computations
Complexity results for classes of quantificational formulas
Unprovability of theorems of complexity theory in weak number theories
Some results on relativized deterministic and nondeterministic time hierarchies
Simulations among multidimensional Turing machines
An analysis of fixed-point queries on binary trees
Oracles for structural properties: The isomorphism problem and public-key cryptography
Multiplication, division, and shift instructions in parallel random access machines
Diagonalization, uniformity, and fixed-point theorems
Hierarchies of Turing machines with restricted tape alphabet size
Augmented loop languages and classes of computable functions
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Polynomial and abstract subrecursive classes
Comparing complexity classes
Minimal pairs of polynomial degrees with subexponential complexity
Relative complexity of checking and evaluating
``V-tape, a virtual memory oriented data type, and its resource requirements
Theory of -languages. I: Characterizations of -context- free languages
-computations on Turing machines
Palindrome recognition in real time by a multitape Turing machine
On splitting recursive sets
The complexity of total order structures
Almost-everywhere complexity hierarchies for nondeterministic time
A note on complexity measures for inductive classes in constructive type theory
Pushdown cellular automata
Succinctness as a source of complexity in logical formalisms
On average time hierarchies
Computational complexity of functions
Separating classes in the exponential-time hierarchy from classes in PH
On transformations of programs
Deterministic multitape automata computations
Time-space tradeoffs for satisfiability
A complexity analysis of bisimilarity for value-passing processes
Complete distributional problems, hard languages, and resource-bounded measure
Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
On relationships between complexity classes of Turing machines
On the complexity of the Leibniz hierarchy
Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces
On the size complexity of hybrid networks of evolutionary processors
Research on the efficient computation mechanism -- in the case of N-vehicle exploration problem
On a possible classification of real-time constructed sequences
Linear-time simulation of multihead Turing machines
The complexity of the word problems for commutative semigroups and polynomial ideals
Fast on-line integer multiplication
Deterministic Turing machines in the range between real-time and linear-time.
Sparse sets and collapse of complexity classes
On the complexity of algebraic numbers
On the lattices of NP-subspaces of a polynomial time vector space over a finite field
Learning secrets interactively. Dynamic modeling in inductive inference
Almost global problems in the LOCAL model
Computing in combinatorial optimization
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
Robust real-time computing with chemical reaction networks
Fractal dimension of assemblies in the abstract tile assembly model
Incremental delay enumeration: space and time
Mahler's method
The efficient computation of aircraft range problem
Unifying known lower bounds via geometric complexity theory
Generality's price: Inescapable deficiencies in machine-learned programs
Continued fractions and transcendental numbers
On the complexity of algebraic numbers. II: Continued fractions
Efficient learning algorithms yield circuit lower bounds
Multitape one-way nonwriting automata
Time-restricted sequence generation
Time- and tape-bounded Turing acceptors and AFLs
The enumerability and invariance of complexity classes
Subrecursive programming languages. II. On program size
k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
Complexity problems in real time languages
Tabulator-Turingmaschine und Komplexität. (Tabulator Turing machine and complexity)
Time-bounded grammars and their languages
On non-determinacy in simple computing devices
Writing stack acceptors
Tape-reversal bounded Turing machine computations
Berechnungen in partiellen Algebren endlichen Typs
Real-time language recognition by one-dimensional cellular automata
An introduction to tile-based self-assembly and a survey of recent results
The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp
Complexity theory basics: NP and NL
A hierarchy of fast reversible Turing machines
\(\mathrm P \overset {?} {=} \mathrm{NP}\)
Reverse complexity
Hartmanis-Stearns Conjecture on Real Time and Transcendence
Programs=data=first-class citizens in a computational world
A Turing test for free will
Improved approximations for hard optimization problems via problem instance classification
scientific article; zbMATH DE number 3644481 (Why is no real title available?)
Efficient algorithms for membership in Boolean hierarchies of regular languages
Some remarks on real numbers induced by first-order spectra
Notes on Levin's theory of average-case complexity
Deciding according to the shortest computations
A Short Introduction to Implicit Computational Complexity

This page was built for publication: On the Computational Complexity of Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5339741)