The density and complexity of polynomial cores for intractable sets

DOI10.1016/S0019-9958(86)80024-9zbMATH Open0611.68021MaRDI QIDQ3751007FDOQ3751007

Pekka Orponen, Uwe Schöning

Publication date: 1986

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

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

zbMATH Keywords

densitycomplexity classesNP-complete setspolynomial complexity coreP-NP-problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (18)

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

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)