scientific article

José L. Balcázar, Joaquim Gabarró, Josep Diaz

Publication date: 5 June 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Turing machines bibliography diagonalization circuit complexity complexity theory structural properties complexity classes structural complexity complete problems polynomial time hierarchy Probabilistic algorithms P-NP-problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Turing machines and related notions (03D10)

Related Items (only showing first 100 items - show all)

Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring ⋮ Logics which capture complexity classes over the reals ⋮ Resource-bounded kolmogorov complexity revisited ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Cellular automata universality revisited ⋮ V-comprehensions and P space ⋮ Some results on uniform arithmetic circuit complexity ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ Self-reducible sets of small density ⋮ Limitations of the upward separation technique ⋮ On monotonous oracle machines ⋮ Machines that perform measurements ⋮ On complexity classes and algorithmically random languages ⋮ On the complexity of small description and related topics ⋮ The degree structure of 1-L reductions ⋮ The emptiness problem for intersections of regular languages ⋮ Empty alternation ⋮ Complexity of EOL structural equivalence ⋮ Almost weakly 2-generic sets ⋮ The complexity of searching implicit graphs ⋮ Type 2 polynomial hierarchies ⋮ On the Complexity of Measurement in Classical Physics ⋮ Faster possibility detection by combining two approaches ⋮ The Power of Machines That Control Experiments ⋮ The malleability of TSP 2Opt ⋮ Adaptive logspace reducibility and parallel time ⋮ A note on the self-witnessing property of computational problems ⋮ On the power of generalized Mod-classes ⋮ The Helping Hierarchy ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ On balanced versus unbalanced computation trees ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ On the computational power of discrete Hopfield nets ⋮ Complexity of E0L structural equivalence ⋮ On the computational power of probabilistic and faulty neural networks ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ UP and the low and high hierarchies: A relativized separation ⋮ New collapse consequences of NP having small circuits ⋮ The complexity of searching succinctly represented graphs ⋮ Extending regular expressions with homomorphic replacement ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ Classes of bounded nondeterminism ⋮ Kronecker's and Newton's approaches to solving: a first comparison ⋮ Graph Isomorphism is in SPP ⋮ A reducibility concept for problems defined in terms of ordered binary decision diagrams ⋮ How much can analog and hybrid systems be proved (super-)Turing ⋮ How Redundant Is Your Universal Computation Device? ⋮ The computational power of parsing expression grammars ⋮ Closest substring problems for regular languages ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle ⋮ Reducibilities on tally and sparse sets ⋮ Limits to measurement in experiments governed by algorithms ⋮ Hyper-polynomial hierarchies and the polynomial jump ⋮ Dot operators ⋮ Calculs sur les structures de langage dénombrable ⋮ Assisted Problem Solving and Decompositions of Finite Automata ⋮ Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P ⋮ Axiomatizing Resource Bounds for Measure ⋮ Complexity Issues for Preorders on Finite Labeled Forests ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ On the Complexity of Szilard Languages of Regulated Grammars ⋮ Do there exist complete sets for promise classes? ⋮ Bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision ⋮ Sets without subsets of higher many-one degree ⋮ A common algebraic description for probabilistic and quantum computations ⋮ A reducibility for the dot-depth hierarchy ⋮ A note on the circuit complexity of PP ⋮ On approximate learning by multi-layered feedforward circuits ⋮ On the typical case complexity of graph optimization ⋮ Logics which capture complexity classes over the reals ⋮ Alternating and empty alternating auxiliary stack automata. ⋮ A note on SpanP functions ⋮ One-way functions and the isomorphism conjecture ⋮ Simple characterizations of $P(\# P)$ and complete problems ⋮ Computational depth and reducibility ⋮ A note on the density of oracle decreasing time-space complexity ⋮ A characterization of the leaf language classes ⋮ Listing graphs that satisfy first-order sentences ⋮ Assembling molecules in ATOMIX is hard ⋮ Sparse sets, approximable sets, and parallel queries to NP ⋮ Finite-valued distance automata ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ On the computational power of dynamical systems and hybrid systems ⋮ The simple dynamics of super Turing theories ⋮ On resource-bounded instance complexity ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ An excursion to the Kolmogorov random strings ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ A reducibility concept for problems defined in terms of ordered binary decision diagrams ⋮ Index sets and presentations of complexity classes ⋮ Toughness, hamiltonicity and split graphs ⋮ On the geometric separability of Boolean functions ⋮ The ARNN model relativises $\mathrm{P}=\mathrm{NP}$ and $\mathrm{P}\neq \mathrm{NP}$ ⋮ Entanglement and the complexity of directed graphs

This page was built for publication: