[Solved]: Whats is the meaning of polynomial run-time in input size ?

Problem Detail: 

If an algorithm runs in exponential time with exponential input then we say it runs in polynomial time ? Why ? Doesn't the algorithm run in exponential time anyway ? How the input size affects ? Thanks.

Asked By : user27500

Answered By : Fizz

I think I understand the question enough to answer it. Yes polynomial time is the time the algorithm takes relative to the size of the input. So if your input has size $n$, PTIME means the running time is a polynomial in $n$. Sure if you replace $n$ with some exponential $n=e^p$ you get an exponential time relative to $p$ (assuming the algorithm was not running in constant time). But that does not invalidate the concept of polynomial time anymore than saying that $f(x)=2x$ is a linear function but you can substitute $x$ with $y^{y^y}$ on both sides, i.e $f(y^{y^y})=2y^{y^y}$; it is an intrinsic property of $f$ of being linear in its argument.

This is further discussed on an example at http://cstheory.stackexchange.com/questions/18756/whats-the-meaning-of-input-size-for-3-sat

This issue of having to express the input size as a function of another "quantity" does occur (implicitly) in the context of reducing one problem to another in order to feed it to an existing algorithm. In that context, in order to avoid the obvious gotcha that would "prove" an EXPTIME problem is a PTIME one by using an exponential-size encoding, only polynomial-time reductions are allowed. So, if $p$ is the size of a problem, you can encode it in PTIME as another problem of size polynomial in $p$. But you can't encode it (taking only PTIME) as problem of exponential size in $p$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38157