Complexity classes without machines: on complete languages for UP

DOI10.1016/0304-3975(88)90022-9zbMath0655.68044OpenAlexW2100570449MaRDI QIDQ1109566

Juris Hartmanis, Hemaspaandra, Lane A.

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6586

zbMATH Keywords

complexity classesunique satisfiabilityBPPcomplete languagescounting class UPprobabilistic classunique accepting paths

Mathematics Subject Classification ID

Related Items (40)

One-way permutations and self-witnessing languages ⋮ A characterization of the leaf language classes ⋮ A note on quadratic residuosity and UP ⋮ An unambiguous class possessing a complete set ⋮ A Parameterized Halting Problem ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Reductions between disjoint NP-pairs ⋮ Structural properties for feasibly computable classes of type two ⋮ Unambiguous computations and locally definable acceptance types ⋮ On the power of parity polynomial time ⋮ Promise problems and access to unambiguous computation ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Optimal proof systems imply complete sets for promise classes ⋮ Robust machines accept easy sets ⋮ On the complexity of ranking ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ On sets polynomially enumerable by iteration ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Separating complexity classes with tally oracles ⋮ P-selectivity: Intersections and indices ⋮ Towards a unified complexity theory of total functions ⋮ A uniform approach to define complexity classes ⋮ On the power of parity polynomial time ⋮ Approximate counting in bounded arithmetic ⋮ LWPP and WPP are not uniformly gap-definable ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ The strong exponential hierarchy collapses ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Dot operators ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ The opacity of backbones ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Randomized Boolean decision trees: Several remarks ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle ⋮ Do there exist complete sets for promise classes? ⋮ On an optimal propositional proof system and the structure of easy subsets of TAUT. ⋮ Kolmogorov characterizations of complexity classes ⋮ On characterizing the existence of partial one-way permutations

Cites Work

• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Relative complexity of checking and evaluating
• On the unique satisfiability problem
• The Boolean Hierarchy I: Structural Properties
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity classes without machines: on complete languages for UP