Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm writing a short document about an integer programming (IP) problem instance.

I've mentioned that IP is known to be NP-Hard, but that being NP-Hard doesn't automatically qualify this particular problem instance to be "hard", as a polynomial algorithm with $O(n^{100^{100}})$ and $n = 10$ is likely to be harder than an NP-Hard problem, also with $n = 10$.

The NP-Hardness is only relevant when comparing problem classes of arbitrary (asymptotic, really) size.

So I've written:

Note that a problem being NP-Hard does not automatically qualify it to be harder than a P problem, for given instances, if the size of the instances are sufficiently small; [here I want a short sentence to say something like how the complexity class is only really relevant when looking at arbitrarily large instances, or something like how the complexity is asymptotic, etc]

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.