Polynomial terse sets
From MaRDI portal
Publication:1104077
DOI10.1016/0890-5401(88)90044-2zbMATH Open0646.68049OpenAlexW2041943346MaRDI QIDQ1104077FDOQ1104077
Authors: Amihood Amir, William Gasarch 
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(88)90044-2
Recommendations
Cites Work
- The complexity of optimization problems
- Title not available (Why is that?)
- On Parallel Searching
- Semirecursive Sets and Positive Reducibility
- The complexity of facets (and some facets of complexity)
- NP is as easy as detecting unique solutions
- The difference and truth-table hierarchies for NP
- The Boolean Hierarchy I: Structural Properties
- Diagonalizations over polynomial time computable sets
- A comparison of polynomial time reducibilities
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- Searching, Merging, and Sorting in Parallel Computation
- Title not available (Why is that?)
- Terse, superterse, and verbose sets
- Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
- On the unique satisfiability problem
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (21)
- One query reducibilities between partial information classes
- Bounded query classes and the difference hierarchy
- A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
- Enumerative counting is hard
- The power of frequency computation
- Meeting of the Association for Symbolic Logic, East Lansing, Michigan, 1988
- Nondeterministic bounded query reducibilities
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Some connections between bounded query classes and non-uniform complexity.
- Time bounded frequency computations
- On computing Boolean connectives of characteristic functions
- A proof of Beigel's cardinality conjecture
- Bounded queries to SAT and the Boolean hierarchy
- Learning recursive functions from approximations
- On resource-bounded instance complexity
- Lower bounds for constant-depth circuits in the presence of help bits
- Bi-immunity results for cheatable sets
- On quasilinear-time complexity theory
- On polynomial-time truth-table reducibility of intractable sets to P-selective sets
- On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
- A relationship between difference hierarchies and relativized polynomial hierarchies
This page was built for publication: Polynomial terse sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104077)
