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 reading A first Course on Logic, (Hedman).

An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion in fewer than $n^k$ steps.

What is this number k? When it says "there's a number $k$", I'm thinking that any number could fill the $k$ and this would make the concept irrelevant.

share|improve this question
    
This number $k$ is some arbitrary constant. What would make you think that this concept is irrelevant. –  sxd Nov 7 '12 at 23:23
    
it's just a short way to write that n^2, n^3, n^4, n^5, ... are all polynomial time –  sperners lemma Nov 7 '12 at 23:24

2 Answers 2

up vote 7 down vote accepted

It doesn’t say there’s a number k: it says that there is a number $k$ that has a certain property. You can’t just pick any old number $k$: it may not have the required property.

Suppose that you have an algorithm that always takes $2^n$ steps to reach its conclusion when the input is of size $n$. Then no such $k$ would exist: no matter what constant $k$ you choose, $2^n>n^k$ for all sufficiently large $n$. You cannot find a constant $k$ such that $2^n\le n^k$ for all $n$. Therefore this is not a polynomial-time algorithm.

Now suppose that you have another algorithm that takes $2n^2+3n+4$ steps to finish when the input is of size $n$. For all $n\ge 4$ we have $2n^2+3n+4<n^3$, so for this algorithm we can choose $k=3$. (The definition is a little inaccurate: it should say that the algorithm reaches its conclusion in fewer than $n^k$ steps for all $n$ greater than some minimum size.)

share|improve this answer
    
I didn't get it, look: For $n=4$, $2^4=16$, I can't understand how is it impossible to find a k for $4^k$, such that $4^k$ > $2^4=16$. –  Vÿska Nov 7 '12 at 23:53
    
@GustavoBandeira, You have to find a fixed $k$ for all such $n$'s not for just one. –  sxd Nov 7 '12 at 23:54
2  
@Gustavo: You do not get to choose a new $k$ for each $n$: you must choose one $k$, and it must work for all $n$ (from some point on). –  Brian M. Scott Nov 7 '12 at 23:56
    
Oh, got it! got it! Thanks for the help, guys. –  Vÿska Nov 7 '12 at 23:59
    
@Gustavo: Great! –  Brian M. Scott Nov 7 '12 at 23:59

The idea is that the number of steps is required to be polynomial in $n$, hence $k$ cannot depend on $n$ and thus has to be a predefined constant.

I'm not sure what more there is to explain.

share|improve this answer

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.