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 want to know if the following proposition is correct or not?

For any integer k, there exists an problem P for which, the minimum possible time complexity of any solution algorithm is $\Omega(n^k)$

Please give me creditable sources such as journal papers, books, etc. about the solution of the above question.

UPDATE: By algorithm I mean standard algorithms as discussed in computational complexity. i.e. an algorithm that for any binary encoded input of size n which corresponds to a problem instance, outputs 0 or 1 (or true or false)

Thanks

share|improve this question
    
Well, that is easy to prove for algorithms - we can just write an alogorithm that stalls for that period of time. The harder question - is there a problem that can only be solved with an alogithm of that complexity - is probably what you really mean. –  Thomas Andrews May 2 '13 at 19:16
    
Why do you need a proof from an outside source? This is simply $k$ nested loops, each iterating $n$ times. –  anorton May 2 '13 at 19:18
    
I corrected my question. That was not what I meant. –  Shayan May 2 '13 at 19:26
add comment

1 Answer

up vote 3 down vote accepted

Alternatively, look for the Time Hierarchy Theorem: http://en.wikipedia.org/wiki/Time_hierarchy_theorem

share|improve this answer
    
Brilliant answer! Thank you. I didn't expect to find the answer here. –  Shayan May 2 '13 at 19:37
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.