scientific article; zbMATH DE number 1142308
From MaRDI portal
Publication:4385524
zbMath0900.68265MaRDI QIDQ4385524
Publication date: 4 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)
Related Items
Invariance properties of RAMs and linear time ⋮ Approximate pattern matching and transitive closure logics. ⋮ Turing Machines for Dummies ⋮ The complexity of first-order and monadic second-order logic revisited ⋮ An existential locality theorem ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ Tight lower bounds for query processing on streaming and external memory data ⋮ Pipelined Decomposable BSP Computers ⋮ Neighbours on a grid ⋮ What is the Church-Turing Thesis? ⋮ PRAM's towards realistic parallelism: BRAM's ⋮ On sharing, memoization, and polynomial time ⋮ Computation as social agency: what, how and who ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ Computing equilibria: a computational complexity perspective ⋮ Shrinking and Expanding Cellular Automata ⋮ Squeezing Feasibility ⋮ Membrane computing and complexity theory: A characterization of PSPACE ⋮ Smoothing the Gap Between NP and ER ⋮ The Communication Hierarchy of Time and Space Bounded Parallel Machines ⋮ On selective unboundedness of VASS ⋮ The complexity of on-line simulations between multidimensional turing machines and random access machines ⋮ The intrinsic difficulty of recursive functions ⋮ Anonymous Processors with Synchronous Shared Memory: Monte Carlo Algorithms ⋮ A canonical form of vector machines ⋮ P systems with proteins on membranes characterize PSPACE ⋮ Weak parallel machines: A new class of physically feasible parallel machine models ⋮ Theory of interaction ⋮ The complexity of the temporal logic with ``until over general linear time ⋮ Morphogenetic computing: computability and complexity results ⋮ Equilibria, fixed points, and complexity classes ⋮ Lower bounds on the computational power of an optical model of computation ⋮ The weak lambda calculus as a reasonable machine ⋮ A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines ⋮ On the computational efficiency of symmetric neural networks ⋮ On quasilinear-time complexity theory ⋮ The computable kernel of abstract state machines ⋮ Realizability models and implicit complexity ⋮ UNWEIGHTED AND WEIGHTED HYPER-MINIMIZATION ⋮ Computability in linear algebra ⋮ Playing Savitch and Cooking Games ⋮ A semantic proof of polytime soundness of light affine logic ⋮ Small fast universal Turing machines ⋮ A formalization of multi-tape Turing machines ⋮ Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer ⋮ Counting nondeterministic computations ⋮ Simulations by Time-Bounded Counter Machines ⋮ Sorting, linear time and the satisfiability problem ⋮ Construction of tree automata from regular expressions ⋮ Difficulties in Forcing Fairness of Polynomial Time Inductive Inference ⋮ Call-by-value lambda calculus as a model of computation in Coq ⋮ Characterizations of periods of multi-dimensional shifts ⋮ Logic and Complexity in Cognitive Science ⋮ Parallel beta reduction is not elementary recursive ⋮ The alternation hierarchy for sublogarithmic space is infinite ⋮ Computational universality and efficiency in morphogenetic systems ⋮ Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
