Polynomial terse sets
From MaRDI portal
Publication:1104077
DOI10.1016/0890-5401(88)90044-2zbMath0646.68049OpenAlexW2041943346MaRDI QIDQ1104077
Amihood Amir, William I. 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
Related Items (21)
A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ The power of frequency computation ⋮ On resource-bounded instance complexity ⋮ Bounded query classes and the difference hierarchy ⋮ Learning recursive functions from approximations ⋮ Meeting of the Association for Symbolic Logic, East Lansing, Michigan, 1988 ⋮ Nondeterministic bounded query reducibilities ⋮ On computing Boolean connectives of characteristic functions ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Time bounded frequency computations ⋮ A proof of Beigel's cardinality conjecture ⋮ Lower bounds for constant-depth circuits in the presence of help bits ⋮ Bi-immunity results for cheatable sets ⋮ Some connections between bounded query classes and non-uniform complexity. ⋮ Bounded queries to SAT and the Boolean hierarchy ⋮ On quasilinear-time complexity theory ⋮ Enumerative counting is hard ⋮ On the complexity of finding the chromatic number of a recursive graph. I: The bounded case ⋮ One query reducibilities between partial information classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of facets (and some facets of complexity)
- Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
- NP is as easy as detecting unique solutions
- The complexity of optimization problems
- Diagonalizations over polynomial time computable sets
- A comparison of polynomial time reducibilities
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Terse, superterse, and verbose sets
- Searching, Merging, and Sorting in Parallel Computation
- On the unique satisfiability problem
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Parallel Searching
- The difference and truth-table hierarchies for NP
- The Boolean Hierarchy I: Structural Properties
- Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
- Semirecursive Sets and Positive Reducibility
This page was built for publication: Polynomial terse sets
