The density and complexity of polynomial cores for intractable sets

DOI10.1016/S0019-9958(86)80024-9zbMath0611.68021MaRDI QIDQ3751007

Pekka Orponen, Uwe Schoening

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

densitycomplexity classesNP-complete setspolynomial complexity coreP-NP-problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

A classification of complexity core lattices ⋮ The structure of generalized complexity cores ⋮ On intractability of the classUP ⋮ Resource bounded randomness and weakly complete problems ⋮ Sets computable in polynomial time on average ⋮ OnP-subset structures ⋮ Constructive complexity ⋮ On ``inherently context-sensitive languages -- an application of complexity cores ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ Exponential-time and subexponential-time sets ⋮ On inefficient special cases of NP-complete problems

This page was built for publication: The density and complexity of polynomial cores for intractable sets