A complexity theory for feasible closure properties
From MaRDI portal
Publication:2366687
DOI10.1016/0022-0000(93)90006-IzbMath0798.68060MaRDI QIDQ2366687
Mitsunori Ogiwara, Hemaspaandra, Lane A.
Publication date: 18 August 1993
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Simple characterizations of \(P(\# P)\) and complete problems, A complexity theory for feasible closure properties, On closure properties of GapP, The operators min and max on the polynomial hierarchy, Cluster computing and the power of edge recognition, Unnamed Item, Languages polylog-time reducible to dot-depth 1/2, Recursion theoretic characterizations of complexity classes of counting functions, Generalized theorems on relationships among reducibility notions to certain complexity classes, Promise problems and access to unambiguous computation, Parameterised counting in logspace, The Shrinking Property for NP and coNP, The shrinking property for NP and coNP, Unnamed Item, Further oracles separating conjectures about incompleteness in the finite domain, The complexity of Bayesian networks specified by propositional and relational languages, The consequences of eliminating NP solutions, Relationships among $PL$, $\#L$, and the determinant, ANALYSIS OF QUANTUM FUNCTIONS, ON HIGHER ARTHUR-MERLIN CLASSES, Quantum and classical complexity classes: Separations, collapses, and closure properties, On the autoreducibility of functions, Lower bounds and the hardness of counting properties, LWPP and WPP are not uniformly gap-definable, The robustness of LWPP and WPP, with an application to graph reconstruction, Unnamed Item, Error-bounded probabilistic computations between MA and AM, Bounded queries to arbitrary sets, P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle, A second step towards complexity-theoretic analogs of Rice's Theorem, Subtractive reductions and complete problems for counting complexity classes, SELF-SPECIFYING MACHINES, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, A common algebraic description for probabilistic and quantum computations, Tally NP sets and easy census functions., A note on unambiguous function classes, Reducing the number of solutions of NP functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic polynomial time is closed under parity reductions
- A low and a high hierarchy within NP
- On the construction of parallel computers from various basis of Boolean functions
- The complexity of combinatorial problems with succinct input representation
- The complexity of optimization problems
- On counting and approximation
- A note on structure and looking back applied to the relative complexity of computable functions
- On the structure of sets in NP and other complexity classes
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- The polynomial-time hierarchy
- Gap-definable counting classes
- PP is closed under truth-table reductions
- A complexity theory for feasible closure properties
- Sublattices of the polynomial time degrees
- The Boolean Hierarchy I: Structural Properties
- The Boolean Hierarchy II: Applications
- The Complexity of Enumeration and Reliability Problems
- Relativized Questions Involving Probabilistic Algorithms
- On the Structure of Polynomial Time Reducibility
- P-Complete Approximation Problems
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- Computational Complexity of Probabilistic Turing Machines
- Lower bounds for the low hierarchy
- Computationally Related Problems
- The complexity of theorem-proving procedures
- On the power of parity polynomial time
- Counting classes: Thresholds, parity, mods, and fewness
