Given the definition for all x ∈ Σ∗

x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1

Lets say the input x = ababab

Then the certificate u shouldn't be longer than p(|x|).

But what would be p(|x|)? In my example?


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.

  • $\begingroup$ Could you give a specific example for such a function, when x=ababab ? $\endgroup$ – simplesystems Jun 25 '18 at 12:11
  • $\begingroup$ The function $p(n) = C$ works, for any $C \geq 0$. $\endgroup$ – Yuval Filmus Jun 25 '18 at 13:02
  • $\begingroup$ sorry maybe i didnt stated it right, t think p was defined as the polynomial length, so the polynomial length of |x|, but what the hell is a polynomial length? $\endgroup$ – simplesystems Jun 25 '18 at 14:16
  • $\begingroup$ There is no such thing as "the polynomial length of |x|" - that's not valid English. $|x|$ is a number. For your $ababab$ example, it's $6$. $p$ is a function, and $p(|x|)$ is that function evaluated at $|x|$ (in your specific case, you'd compare whether the length of $u$ is less than $p(6)$). $p$ has to be a polynomial function, so $p(x)$ could be $x^2$ or $x^3$ or $x^{100}$ (etc...) but it wouldn't be allowed to be something not-polynomial like $2^x$ or $x!$. $\endgroup$ – Tom van der Zanden Jun 25 '18 at 14:40
  • $\begingroup$ ok, thats great I am almost there... and who specifies this polynomial function? does this function has something in common with the turing machine itself? meaning is the time or space complexity equally this function? or are this two complete different things? $\endgroup$ – simplesystems Jun 25 '18 at 15:37

A language $L$ is in NP if there exists a polynomial $p$ and a Turing machine $M$ running in polynomial time such that $$ x \in L \text{ iff there exists } u \in \Sigma^* \text{ with } |u| \leq p(|x|) \text{ such that } M(x,u) = 1. $$ Asking what is $p$ is exactly the same as asking what is $M$. When proving that a language is in NP, we have to specify both $p$ and $M$.

  • $\begingroup$ sorry maybe I didnt stated it right, I think p was defined as the polynomial length, so the polynomial length of |x|, but what the hell is a polynomial length? $\endgroup$ – simplesystems Jun 25 '18 at 14:17
  • $\begingroup$ I suggest you forget about your definition, and stick to mine. $\endgroup$ – Yuval Filmus Jun 25 '18 at 14:52
  • $\begingroup$ I do not see a difference in your definition to mine $\endgroup$ – simplesystems Jun 25 '18 at 14:56
  • $\begingroup$ My definition doesn't contain the phrase polynomial length, which you don't like. $\endgroup$ – Yuval Filmus Jun 25 '18 at 14:59
  • $\begingroup$ I'm not sure if I dont like it, I just dont know what it is. $\endgroup$ – simplesystems Jun 25 '18 at 15:09

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.