scientific article; zbMATH DE number 719756
From MaRDI portal
Publication:4321931
zbMath0826.68048MaRDI QIDQ4321931
José L. Balcázar, Joaquim Gabarró, Josep Diaz
Publication date: 6 February 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Collapse of PP with a semi-random source to BPP, A degree bound on decomposable trees, Computational depth: Concept and applications, Computing queries with higher-order logics, The operators min and max on the polynomial hierarchy, The complexity of generating test instances, Nondeterministic functions and the existence of optimal proof systems, Query order in the polynomial hierarchy, On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP, Unnamed Item, On efficiency of notations for natural numbers, Nonuniform reductions and NP-completeness, Recursion theoretic characterizations of complexity classes of counting functions, Average-case intractability vs. worst-case intractability, The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures, Nontriviality for exponential time w.r.t. weak reducibilities, Question answering by humans and machines: a complexity-theoretic view, How We Think of Computing Today, P-immune sets with holes lack self-reducibility properties., On the Complexity of Equilibria Problems in Angel-Daemon Games, Upper bounds on ATSP neighborhood size., On the Degree of Extension of Some Models Defining Non-Regular Languages, Base invariance of feasible dimension, Hard sets are hard to find, Almost complete sets., Equilibria problems on games: complexity versus succinctness, Oracles and Advice as Measurements, Characterizing the super-Turing computing power and efficiency of classical fuzzy Turing machines, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Reversal complexity revisited, Data independence of read, write, and control structures in PRAM computations, A second step toward the strong polynomial-time hierarchy, The complexity of stochastic sequences, Baire categories on small complexity classes and meager-comeager laws, On the asymmetric complexity of the group-intersection problem, Parallel algorithms for separable permutations, Expressibility of Higher Order Logics, On the degrees of non-regularity and non-context-freeness, The P\(\neq\) NP conjecture in the context of real and complex analysis, On pseudorandomness and resource-bounded measure, Prediction and dimension, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, If P \(\neq\) NP then some strongly noninvertible functions are invertible, Closure and nonclosure properties of the classes of compressible and rankable sets, Exponential separation of quantum and classical online space complexity, Polylog depth, highness and lowness for E, Some complexity bounds for subtype inequalities, Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets, Weak completeness notions for exponential time, The zero-one law holds for BPP, On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering, The Projective Noether Maple Package: Computing the dimension of a projective variety, On an optimal propositional proof system and the structure of easy subsets of TAUT., Recursive computational depth., Sparse sets and collapse of complexity classes, Degrees of Dowd-type generic oracles, Complexity of the \(r\)-query tautologies in the presence of a generic oracle
