3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented May 2, 2013 at 19:16
  • $\begingroup$ Why do you need a proof from an outside source? This is simply $k$ nested loops, each iterating $n$ times. $\endgroup$ Commented May 2, 2013 at 19:18
  • $\begingroup$ I corrected my question. That was not what I meant. $\endgroup$ Commented May 2, 2013 at 19:26

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Brilliant answer! Thank you. I didn't expect to find the answer here. $\endgroup$ Commented May 2, 2013 at 19:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.