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

Question

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.

Answer 1

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$.

Answer 2

To add a new perspective to Steven's answer, I think you missed a crucial part of NP: Yes, the output's size must be polynomial in the input's size, but furthermore, the "guessed" string must allow verification in polynomial time.

For this, it is often helpful to not consider the decision variants, by the search variants for problems, i.e., if possible, don't only output TRUE, but also a solution (e.g., for 3SAT, a satisfying interpretation).

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.