The density and complexity of polynomial cores for intractable sets
From MaRDI portal
Publication:3751007
DOI10.1016/S0019-9958(86)80024-9zbMath0611.68021MaRDI QIDQ3751007
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
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