0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Keep in mind that non-deterministic $\neq$ randomized. $\endgroup$
    – Nathaniel
    May 20 at 16:01
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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