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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ You may be confused with "input size" and "input value". If so, see this post. (If not, I am afraid that you should make your questions a bit more specific.) $\endgroup$– hengxinFeb 9, 2015 at 11:08
-
$\begingroup$ See also: cs.stackexchange.com/questions/24484/… $\endgroup$– GuildensternFeb 9, 2015 at 12:27
-
$\begingroup$ "Exponential time on exponential input" -- with respect to what? $\endgroup$– Raphael ♦Feb 9, 2015 at 13:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 https://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$.
