scientific article
From MaRDI portal
Publication:3996675
zbMath0746.68032MaRDI QIDQ3996675
Joaquim Gabarró, José L. Balcázar, Josep Diaz
Publication date: 17 September 1992
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Some descriptive-set-theoretical problems in complexity theory, The guarded fragment with transitive guards, Logics which capture complexity classes over the reals, Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits, The operators min and max on the polynomial hierarchy, Bi-immunity separates strong NP-completeness notions, The complexity of generating test instances, Locating \(P\)/poly optimally in the extended low hierarchy, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, Some results concerning two-dimensional turing machines and finite automata, On resource-bounded instance complexity, Cluster computing and the power of edge recognition, An excursion to the Kolmogorov random strings, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, On the complexity of the two-variable guarded fragment with transitive guards, Language classes defined by time-bounded relativised cellular automata, Separating classes in the exponential-time hierarchy from classes in PH, Computational complexity of logical theories of one successor and another unary function, An observation on probability versus randomness with applications to complexity classes, A broader view on the limitations of information processing and communication by nature, Nontriviality for exponential time w.r.t. weak reducibilities, The ARNN model relativises \(\mathrm{P}=\mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\), On complexity classes and algorithmically random languages, Graph layout problems, Degrees and reducibilities of easy tally sets, Empty alternation, Approximation of coNP sets by NP-complete sets, Computations with oracles that measure vanishing quantities, Sets computable in polynomial time on average, An oracle builder's toolkit, Optimal proof systems imply complete sets for promise classes, Adaptive logspace reducibility and parallel time, The Helping Hierarchy, A recursion-theoretic approach to NP, END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS, On logics with two variables, Two queries, Hard sets are hard to find, On the computational complexity of behavioral description-based web service composition, Immunity and pseudorandomness of context-free languages, A personal account of Turing's imprint on the development of computer science, Recursion Schemata for NC k, On some derivation mechanisms and the complexity of their Szilard languages, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Reversal complexity revisited, On random oracle separations, Data independence of read, write, and control structures in PRAM computations, Nondeterministic, probabilistic and alternating computations on cellular array models, Helping by unambiguous computation and probabilistic computation, A weak version of the Blum, Shub, and Smale model, Fine hierarchies and m-reducibilities in theoretical computer science, A survey of space complexity, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, Baire categories on small complexity classes and meager-comeager laws, NC algorithms for real algebraic numbers, Complexity of logical theories involving coprimality, Comparing nontriviality for E and EXP, Unambiguity of circuits, On the expressibility and the computability of untyped queries, THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY, On pseudorandomness and resource-bounded measure, Graph Isomorphism is in SPP, On Toda’s Theorem in Structural Communication Complexity, Structural properties of oracle classes, On the Restraining Power of Guards, Limits to measurement in experiments governed by algorithms, 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, Exponential-time and subexponential-time sets, A positive relativization of polynomial time versus polylog space, Double-exponential inseparability of Robinson subsystem Q+, Polylog depth, highness and lowness for E, Complexity Issues for Preorders on Finite Labeled Forests, On sets bounded truth-table reducible to $P$-selective sets, The polynomial hierarchy of functions and its levels, Some complexity bounds for subtype inequalities, Weak completeness notions for exponential time, The zero-one law holds for BPP, Theory of one-tape linear-time Turing machines, Some aspects of studying an optimization or decision problem in different computational models, Saturation and stability in the theory of computation over the reals, A reducibility for the dot-depth hierarchy, Resource bounded immunity and simplicity, Degrees of sets having no subsets of higher m- and t t-degree, Bounded queries, approximations, and the Boolean hierarchy, Sparse sets and collapse of complexity classes, The relative power of logspace and polynomial time reductions, On symmetric differences of NP-hard sets with weakly P-selective sets, The complexity of achievement and maintenance problems in agent-based systems
