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
add comment

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.