Polynomial terse sets

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

zbMATH Keywords

NP-completepolynomial timeBoolean hierarchyterse sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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