Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
3 edited body
source | link

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $x$$u$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $x$$u$ is indeed a valid vertex cover.

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $x$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $x$ is indeed a valid vertex cover.

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $u$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $u$ is indeed a valid vertex cover.

2 added 348 characters in body
source | link

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $x$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $x$ is indeed a valid vertex cover.

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $x$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $x$ is indeed a valid vertex cover.

1
source | link

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.