The density and complexity of polynomial cores for intractable sets

DOI10.1016/S0019-9958(86)80024-9MaRDI QIDQ3751007zbMATH OpenFDO

Authors Pekka Orponen, Uwe Schöning

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)

Recommendations

• scientific article; zbMATH DE number 3887072
• On inefficient special cases of NP-complete problems
• A classification of complexity core lattices
• scientific article; zbMATH DE number 3913678
• scientific article; zbMATH DE number 403953

Cited in

(19)

• On intractability of the classUP
• scientific article; zbMATH DE number 403953 (Why is no real title available?)
• scientific article; zbMATH DE number 3913678 (Why is no real title available?)
• On the polynomial IO-complexity
• Kolmogorov complexity cores
• scientific article; zbMATH DE number 3887072 (Why is no real title available?)
• Computation times of NP sets of different densities
• On ``inherently context-sensitive languages -- an application of complexity cores
• Constructive complexity
• Sets computable in polynomial time on average
• Resource bounded randomness and weakly complete problems
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• On inefficient special cases of NP-complete problems
• A classification of complexity core lattices
• The structure of generalized complexity cores
• Exponential-time and subexponential-time sets
• scientific article; zbMATH DE number 1555981 (Why is no real title available?)
• OnP-subset structures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751007)