Are there any known "hard" instances for NP-Complete Problems,

or are there no general hard instances. So for different algorithms different instances are hard?


closed as unclear what you're asking by D.W., Pål GD, Luke Mathieson, David Richerby, Rick Decker Feb 19 '15 at 1:56

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ ... where "hard" means an NP-hard distribution or that there is no known polynomial-time algorithm for the distribution? $\;$ $\endgroup$ – user12859 Feb 18 '15 at 16:49
  • 1
    $\begingroup$ No single instance can be hard, since it is hard-coded. There could be an infinite sequence of instances which is hard in the sense that if some polytime algorithm works correctly on all of them, then P=NP. The set of all instances is such an example, but sometimes smaller sets also work. $\endgroup$ – Yuval Filmus Feb 18 '15 at 17:28
  • $\begingroup$ and many instance can be trivially solved, but then there has to be a minimum set of the "hard" instances! But is there anything known, where these instances lie, how do they look like? $\endgroup$ – guest Feb 18 '15 at 17:48
  • 1
    $\begingroup$ Why does there have "to be a minimum set of the 'hard' instances"? $\;$ $\endgroup$ – user12859 Feb 18 '15 at 18:30
  • $\begingroup$ Wouldn't otherwise all instance be easy? $\endgroup$ – guest Feb 18 '15 at 18:33

Browse other questions tagged or ask your own question.