Polynomial terse sets
type: Item
instance of: scholarly article
title: Polynomial terse sets
zbMATH Open document ID: 0646.68049
DOI: 10.1016/0890-5401(88)90044-2
author: Amihood Amir
author: William Gasarch
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4055035
zbMATH Keywords: terse sets
zbMATH Keywords: polynomial time
zbMATH Keywords: NP-complete
zbMATH Keywords: Boolean hierarchy
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90044-2
OpenAlex ID: W2041943346
cites work: Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
cites work: Diagonalizations over polynomial time computable sets
cites work: Terse, superterse, and verbose sets
cites work: On the unique satisfiability problem
cites work: The Boolean Hierarchy I: Structural Properties
cites work: Q3751004
cites work: Q3862379
cites work: Semirecursive Sets and Positive Reducibility
cites work: The difference and truth-table hierarchies for NP
cites work: The complexity of optimization problems
cites work: Searching, Merging, and Sorting in Parallel Computation
cites work: A comparison of polynomial time reducibilities
cites work: The complexity of facets (and some facets of complexity)
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
cites work: On Parallel Searching
cites work: NP is as easy as detecting unique solutions
cites work: Q3766851
cites work: Q3703297
cites work: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
description: scientific article; zbMATH DE number 4055035