Paper Info
Title
Complexity cores and hard problem instances
Abstract
Many intractable problems such as NP-complete problems (provided PNP) have easy subproblems. In contrast, we investigate the existence and the properties of inherently hard subproblems, called complexity cores. Furthermore, the question is posed whether individual problem instances can be inherently hard (for all algorithms solving the problem), and this question is answered positively.
Year
DOI
Venue
1990
10.1007/3-540-52921-7_72
SIGAL International Symposium on Algorithms
Keywords
Field
DocType
hard problem instances,hard problem instance,complexity cores,complexity core,np complete problem
Computer science,Theoretical computer science,Complete
Conference
Volume
ISSN
ISBN
450
0302-9743
0-387-52921-7
Citations 
PageRank 
References 
2
0.41
19
Authors
1
Name
Order
Citations
PageRank
Uwe Schöning1998105.69