# Is every problem with an output's size that grows polynomialy np?

I am wondering if every problem with an output's size that grows polynomialy is $$\textsf{NP}$$?

My thinking is every $$\textsf{NP}$$ problems can be solved in polynomial time by a non-deterministic Turing machine. (Wikipedia)

Moreover, consider a non-deterministic algorithm, that takes in input an integer $$n$$ and an integer $$k$$. This algorithm randomly outputs an $$n^k$$ bits combination. For example $$(2,2)$$ could output $$0101$$

Intuitively, this algorithm as a polynomial complexity.

A problem with an output's size that grows polynomialy could be solved by this algorithm.

Therefore, a problem with an output's size that grows polynomialy could be solved by a non-deterministic algorithm in polynomial time.

Therefore, every problem with an output's size that grows polynomialy is $$\textsf{NP}$$.

I do not know, if my thinking is correct.

• Keep in mind that non-deterministic $\neq$ randomized. May 20 at 16:01

No. All problems in $$\mathsf{NP}$$ are decision problems and, as such, the size of their output is trivially polynomially bounded (the output is just one bit). Moreover, there are decision problems that are not in $$\mathsf{NP}$$. Indeed, by time hierarchy theorem $$\mathsf{NTIME}(n^k) \subsetneq \mathsf{NTIME}(2^n)$$ for every constant $$k$$.
The textbook example would be deciding if a Turing Machine M halts in time $$O(2^{\langle M \rangle})$$. The output for the decision problem is one bit, but the verification string has exponential length and is thus not verifiable in time polynomial in the input's size.