# Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP? [duplicate]

I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and couldn't think of a way to disprove it to myself. Perhaps it

Obviously, the algorithm described in the title would have to iterate 2^n times to print all numbers from 1 to 2^n. As a result, this algorithm would never be able to be done in polynomial time and P is indeed a proper subset of NP. What is the error in my reasoning here? Is it that this problem is not in NP?

## marked as duplicate by David Richerby, Luke Mathieson, Community♦Nov 21 '17 at 1:15

• How do you go from “this algorithm would never be able to be done in polynomial time” to “P is indeed a proper subset of NP”? – Gilles 'SO- stop being evil' Nov 21 '17 at 0:59
• It is my (basic) understanding that the problems in NP are those not able to be solved in polynomial time. Thus, the described problem would be in NP, but definitely not in P because it can never be done in polynomial time. – tchar989 Nov 21 '17 at 1:01
• NP is a particular set of problems, some of which we don't know how to do in polynomial time. It isn't just "not polynomial." Also, P and NP are sets of decision problems and "count to $2^n$" isn't a decision problem. – David Richerby Nov 21 '17 at 1:10

Note that “problem” has a specific technical meaning: it's a decision problem, i.e. an function from some input space to $\{\mathrm{yes}, \mathrm{no}\}$.
If you found a decision problem that cannot be solved in less than $2^n$ steps where $n$ is the size of the input, then that problem would not be in P. It might not be in NP either: it would only be in NP if there was a way to verify a solution in polynomial time.