Polynomial terse sets

DOI10.1016/0890-5401(88)90044-2MaRDI QIDQ1104077zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

NP-completepolynomial timeBoolean hierarchyterse sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Approximable sets
• Near-Testable Sets
• Terse, superterse, and verbose sets
• NP-hard sets are superterse unless NP is small
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Cites work

• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3988706 (Why is no real title available?)
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Diagonalizations over polynomial time computable sets
• Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
• NP is as easy as detecting unique solutions
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• On Parallel Searching
• On the unique satisfiability problem
• Searching, Merging, and Sorting in Parallel Computation
• Semirecursive Sets and Positive Reducibility
• Terse, superterse, and verbose sets
• The Boolean Hierarchy I: Structural Properties
• The complexity of facets (and some facets of complexity)
• The complexity of optimization problems
• The difference and truth-table hierarchies for NP

Cited in

(21)

• A relationship between difference hierarchies and relativized polynomial hierarchies
• Bounded query classes and the difference hierarchy
• One query reducibilities between partial information classes
• 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
• Some connections between bounded query classes and non-uniform complexity.
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Time bounded frequency computations
• On computing Boolean connectives of characteristic functions
• Bounded queries to SAT and the Boolean hierarchy
• A proof of Beigel's cardinality conjecture
• 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 the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• On polynomial-time truth-table reducibility of intractable sets to P-selective sets

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)