Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.