0
$\begingroup$

Assuming that the input $n$ is given as a decimal number.
I was asked to prove whether the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ is computable in polynomial time using TM or not.

My guess is that the function cannot be computed in polynomial time but I can't figure out how I can prove it.
Showing that the function can be computed in polynomial time is easy because we just have to exhibit an algorithm and show it runs in polynomial time.

I was trying to think about the problem a little bit but I feel like I don't have the right knowledge and tools when it comes to understanding the relationship between a function that can\cannot be computed in polynomial time and a language that can be decided in polynomial time ? and how it's related to the problem of $P = NP$ ?

My TA said that I should use a certain property that the function above has in order to show that it can't be computed in polynomial time, but he didn't answer the question about the relationship between computable\non-computable functions to decidable\non-decidable languages.

$\endgroup$

1 Answer 1

4
$\begingroup$

Look at the size of the required output. How much time would it take you just to write the result?

And this has nothing to do whatsoever with P vs NP, or computable or decidable languages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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