On the Computational Complexity of Algorithms

Related Items

The strong exponential hierarchy collapses, Weak completeness in \(\text{E}\) and \(\text{E}_{2}\), The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Multihead two-way probabilistic finite automata, On the power of several queues, Linear speed-up does not hold on Turing machines with tree storages, A speed-up theorem without tape compression, Resource restricted computability theoretic learning: Illustrative topics and problems, Speed-up theorems in type-2 computations using oracle Turing machines, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, Data structures for distributed counting, The complexity of two-player games of incomplete information, Time hierarchies for cryptographic function inversion with advice, Computing equilibria: a computational complexity perspective, Accepting networks of splicing processors: complexity results, Complexity-theoretic algebra. II: Boolean algebras, Parametrization over inductive relations of a bounded number of variables, When is arithmetic possible?, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, 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 \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages, \(\omega\)-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, On the size complexity of hybrid networks of evolutionary processors, 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, 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, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Unnamed Item, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, A note on the complexity of program evaluation, Towards separating nondeterminism from determinism, Indistinguishability and First-Order Logic, Computability and Complexity in Self-assembly, Dynamic Modeling in Inductive Inference, Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines, Relationships between pushdown automata with counters and complexity classes, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Real-time computations with restricted nondeterminism, An application of the translational method, Alternating time versus deterministic time: A separation, Production en temps réel et complexité de structure de suites infinies, The complexity of type inference for higher-order typed lambda calculi, Unnamed Item, The theory of languages, Counter machines and counter languages, Real-time solutions of the origin-crossing problem, Quasi-realtime languages, [https://portal.mardi4nfdi.de/wiki/Software:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung], The theory of languages, Komplexität von Algorithmen mit Anwendung auf die Analysis, Computational complexity of random access stored program machines, On restricted turing computability, A unified approach to the definition of random sequences, Multi-stack-counter languages, On the Minimum Computation Time of Functions, Uniform tag sequences, Lower bounds for multiplayer noncooperative games of incomplete information

Cites Work