1
$\begingroup$

Decision Problem: Is $2^k$ + $M$ NOT a prime?

$K$ and $M$ are our inputs represented as integers.

Function Variant: Output the result of $2^k$ + $m$

We can consider, $M$ = $0$.

Proof that calculating 2^n requires an exponential amount of digits as the result

Question

Is it true that a non-deterministic machine cannot output $2^n$ (exponential) digits in polynomial time?

Does this mean that the problem is not in $FNP$?

Improve this question
$\endgroup$
2
  • $\begingroup$ $FNP$ != $FEXPTIME$?? $\endgroup$
    – The T
    Commented Aug 14, 2020 at 4:56
  • $\begingroup$ @D.W I updated the question, let me know of anything else that confuses you. $\endgroup$
    – The T
    Commented Aug 14, 2020 at 15:31

1 Answer 1

Reset to default
2
$\begingroup$

When we say that an algorithm runs in polynomial time, we mean that its running time is at most a polynomial of the length of the input. I assume the input is an integer $n$. The usual way to represent integers is in binary; then the integer $n$ requires $\lg n$ bits to represent. Therefore, a polynomial-time algorithm will have a running time that is at most $p(\lg n)$, where $p$ is some polynomial.

In each step of computation, the algorithm can output at most one item (e.g., $O(1)$ bits of output). So, an algorithm with polynomial running time $p(\lg n)$ can output at most $p(\lg n)$ digits of output, for some polynomial $p$. You can think of this as at most $(\lg n)^c$ digits of output, for some constant $c$ (the constant $c$ will depend on the algorithm).

Now, $2^n$ is asymptotically much larger than $(\lg n)^c$. So, no, a polynomial-time machine cannot $2^n$ digits, when given $n$ as input.

What if the machine is non-deterministic? The same is still true. Non-deterministic means that there are multiple possible branches that the computation could follow. But for each branch, it's still true that the length of the output can be no longer than the number of steps of computation. So, each branch of the non-deterministic computation is limited to outputting at most $(\lg n)^c$ digits.

You might be wondering, what is the output of a non-deterministic machine? Well, that's not a well-defined question. Instead, for a non-deterministic machine, we can talk about the set of possible outputs. If it is a polynomial-time machine, then there are a set of possible outputs, but they will all be polynomial in length. So, a string of $2^n$ digits cannot be among the set of possible outputs; it's too long.

I sense that you are somewhat new to computational complexity. I suggest that you try to avoid thinking about "function" complexity classes until you are really solid on the "decision" complexity classes. I find the decision classes easier to think about, and the function classes harder to think about.

Is the problem in FNP? Well, probably it will be most useful to refer to the definition of FNP. I'm out of time to look that up right now and check it carefully, but I expect you're going to find that the answer is 'no', because the definition requires (explicitly or implicitly) that the length of the output be at most a polynomial in the length of the input.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I've actually seen two definitions of FNP: a predicate-based one and as a search problem. Is there a reliable source which states which one is correct? $\endgroup$
    – user114966
    Commented Aug 14, 2020 at 17:50
  • 1
    $\begingroup$ @Dmitry, no. I think both are correct. It's analogous to NP: there are two definitions, one as as a set of decision problems that can be computable by a polynomial-time non-deterministic algorithm, another as a verifier (a binary relation) that has a deterministic polynomial-time algorithm. I've revised my answer. Regardless of which definition you use, you'll come to the same conclusion regarding the original question. $\endgroup$
    – D.W. ♦
    Commented Aug 14, 2020 at 17:55
  • $\begingroup$ If I understand the definitions correctly, they are not equivalent: for factorization ($P(x,y)=$ $y>1$ and $y$ divides $x$), checking $P(x,y)$ is probably easier than finding such $y$. $\endgroup$
    – user114966
    Commented Aug 14, 2020 at 18:00
  • $\begingroup$ Ah, our search Turing machine is non-deterministic (so we can non-deterministically try all such $y$), so they are equivalent, right? But in general we don't know when we should stop our search (we only know that $|y| = poly(|x|)$, but don't have an exact bound). $\endgroup$
    – user114966
    Commented Aug 14, 2020 at 18:03
  • 1
    $\begingroup$ @Dmitry, as far as I see, they are indeed equivalent. It doesn't matter that you don't have the exact bound because the definitions are existencial. If you know there is a machine M that verifies (x,y) in time polynomial with respect to x, then you know y <= p(x) for some polynomial p, even if you don't know p. Then there is necessarily a NTM M' that guesses y for every x and then checks before accepting (leaving y on the tape). M' is of course dependent on p. It is true that as we don't know p we don't know how M' looks like, but we know it exists, because such a p exists by definition. $\endgroup$
    – Bernardo Subercaseaux
    Commented Aug 14, 2020 at 19:15

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.