Skip to main content
deleted 575 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. In your case, we'd define a binary relation where $x$ is the input (an encoding of an integer $n$) and $y$ is the output (we hopeprobably it will be $2^n$). Thus, $P(x,y)$ is true iff $y=2^x$ (viewing $x,y$ as encodings of integers). Then, check whether that $P(x,y)$ meets the conditions inmost useful to refer to the definition of FNP. If you try I'm out of time to dolook that up right now and check it carefully, you'llbut I expect you're going to find that the key clause inanswer is 'no', because the Wikipedia definition is "whererequires $y$ is(explicitly or implicitly) that the length of the output be at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic conceptspolynomial in computational complexity, such as formal languages, decision problems, P, NP, etcthe length of the input.

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. In your case, we'd define a binary relation where $x$ is the input (an encoding of an integer $n$) and $y$ is the output (we hope it will be $2^n$). Thus, $P(x,y)$ is true iff $y=2^x$ (viewing $x,y$ as encodings of integers). Then, check whether that $P(x,y)$ meets the conditions in the definition. If you try to do that, you'll find that the key clause in the Wikipedia definition is "where $y$ is at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic concepts in computational complexity, such as formal languages, decision problems, P, NP, etc.

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.

deleted 2 characters in body
Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. Strictly speaking In your case, you haven't definedwe'd define a binary relation so there's nothing to ask about whether itwhere $x$ is in FNP yetthe input (an encoding of an integer $n$) and $y$ is the output (we hope it will be $2^n$). More loosely speaking Thus, first you'd need to see if there$P(x,y)$ is a way to define a binary relation based on your problemtrue iff $y=2^x$ (viewing $x,y$ as encodings of integers). Then, and then see ifcheck whether that binary relation$P(x,y)$ meets thosethe conditions in the definition. If you try to do that, I think you mightyou'll find that the key clause in the Wikipedia definition is "where $y$ is at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic concepts in computational complexity, such as formal languages, decision problems, P, NP, etc.

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. Strictly speaking, you haven't defined a binary relation so there's nothing to ask about whether it is in FNP yet. More loosely speaking, first you'd need to see if there is a way to define a binary relation based on your problem, and then see if that binary relation meets those conditions. If you try to do that, I think you might find that the key clause in the Wikipedia definition is "where $y$ is at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic concepts in computational complexity, such as formal languages, decision problems, P, NP, etc.

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. In your case, we'd define a binary relation where $x$ is the input (an encoding of an integer $n$) and $y$ is the output (we hope it will be $2^n$). Thus, $P(x,y)$ is true iff $y=2^x$ (viewing $x,y$ as encodings of integers). Then, check whether that $P(x,y)$ meets the conditions in the definition. If you try to do that, you'll find that the key clause in the Wikipedia definition is "where $y$ is at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic concepts in computational complexity, such as formal languages, decision problems, P, NP, etc.

Source Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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, use the definition. Wikipedia says that FNP is a set of binary relations, and gives a condition for a binary relation $P(x,y)$ to be in FNP. Strictly speaking, you haven't defined a binary relation so there's nothing to ask about whether it is in FNP yet. More loosely speaking, first you'd need to see if there is a way to define a binary relation based on your problem, and then see if that binary relation meets those conditions. If you try to do that, I think you might find that the key clause in the Wikipedia definition is "where $y$ is at most polynomially longer than $x$"; which your problem will not satisfy. If that is too vague, I suggest finding a good textbook and following the exposition in it. This may require you to first study more basic concepts in computational complexity, such as formal languages, decision problems, P, NP, etc.