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

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, Gap-languages and log-time complexity classes, On Goles' universal machines: a computational point of view, The isomorphism conjecture for constant depth reductions, An oracle builder's toolkit, Optimal proof systems imply complete sets for promise classes, Test sets for the universal and existential closure of regular tree languages., On the simulation of quantum Turing machines., Downward translations of equality, Non-uniform reductions, Max NP-completeness made easy, Two queries, On the computational complexity of behavioral description-based web service composition, Book review of: S. Arora and B. Barak, Computational complexity: a modern approach., Relations between average-case and worst-case complexity, Strong and robustly strong polynomial-time reducibilities to sparse sets, Bounded queries to SAT and the Boolean hierarchy, Polynomial recognition of equal unions in hypergraphs with few vertices of large degree, On random oracle separations, On p-creative sets and p-completely creative sets, A bounded arithmetic AID for Frege systems, $P$-sufficient statistics for PAC learning $k$-term-DNF formulas through enumeration, Succinct circuit representations and leaf language classes are basically the same concept, Approximate solution of NP optimization problems, On quasilinear-time complexity theory, Some results on selectivity and self-reducibility, A note on Mod and generalised Mod classes, Modulo classes and logarithmic advice, If NP has polynomial-size circuits, then MA=AM, Helping by unambiguous computation and probabilistic computation, A weak version of the Blum, Shub, and Smale model, Almost everywhere high nonuniform complexity, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, Fine hierarchies and m-reducibilities in theoretical computer science, A survey of space complexity, On polynomial-time Turing and many-one completeness in PSPACE, A note on two-way probabilistic automata, Universal relations and {\#}P-completeness, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets, If not empty, NP-P is topologically large, Verification of qualitative $\mathbb Z$ constraints, Sparse selfreducible sets and nonuniform lower bounds, Complexity of logical theories involving coprimality, Deciding bisimilarity is P-complete, Comparing nontriviality for E and EXP, Model checking abilities of agents: a closer look, On the computational complexity of integral equations, Unambiguity of circuits, Circuit size relative to pseudorandom oracles, TANTRIX$^{\text{TM}}$ rotation puzzles are intractable, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Proof systems that take advice, Structural properties of oracle classes, An algorithm for implicit interpolation, On 1-truth-table-hard languages, A positive relativization of polynomial time versus polylog space, A note on sparse sets and the polynomial-time hierarchy, The price of universality, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Resource bounded randomness and computational complexity, Undecidability results for low complexity time classes, Exact learning via teaching assistants, The counting complexity of group-definable languages, Stochastic analog networks and computational complexity, Saturation and stability in the theory of computation over the reals, On the Hamming distance of constraint satisfaction problems., Deterministic Turing machines in the range between real-time and linear-time., The alternation hierarchy for sublogarithmic space is infinite, Représentations des nombres réels par développements en base entière et complexité. (Representations of real numbers by expansions on integer basis and complexity), A modal perspective on the computational complexity of attribute value grammar, Transfer theorems via sign conditions, An upward measure separation theorem, On the computational structure of the connected components of a hard problem, Relativized separation of EQP from $\text{P}^{\text{NP}}$, Multi-head finite automata: Data-independent versus data-dependent computations, Multi-modal diagnosis combining case-based and model-based reasoning: a formal and experimental analysis, One complexity theorist's view of quantum computing