0
$\begingroup$

Let $L \subset \sigma^*$ be a decision problem. An Algorithim M is a polynomial bounded verifier for $L$, when:

M has a polynomial bounded run time

$M(x,z)$ the output on the the input $x \text{#} z$. Then it's true that:

$ x \in L <=> \exists z \in \{ 0,1 \}^{p(|x|)} :M(x,z)=1$, for a polynomial $p: \mathbb{N} \to \mathbb{N}$

NP denotes the class of decision problems for which there exists a polynomial bounded verifier

I am having a lot of trouble understanding the above definitions. I have a few questions:

  1. Why do binary strings pop up here?
  2. Why do we evaluate a polynomial on the absolute value of $|x|$?
  3. Doesn't this assume that somehow we can embed our problems in terms of problems related to string solving? Doesn't this limit the set of problems we can study theoritically?

Thanks.

Remark: This is my first course on theoritical computer science, and it maybe that the question is a complete noob question, please let me know if it is.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

  1. It could have been ternary strings, or strings over the alphabet $\{\text{h},\text{a},\text{r},\text{d}\}$, but binary is by far the most standard choice (I assume that you agree that binary is the standard for low level computation). The important part here is that, if we have a string over a different alphabet, say $\{\text{h},\text{a},\text{r},\text{d}\}$, we could choose to represent letters in binary as for example $\text{h} \mapsto 1, \text{a} \mapsto 01, \text{r} \mapsto 001, \text{d} \mapsto 0001$. This way $\text{darh} \mapsto 0001010011$, and you can notice that there is no ambiguity for decoding this back. So in general, allowing a constant but > 2 number of symbols won't change asymptotics. In contrast, it is important that we don't use unary strings: $\{1\}^\star$, as in this case there's only one possible string of any given length $n$, and thus NP-completeness of any unary language would imply P = NP.

  2. We evaluate it on the length of $x$, denoted $|x|$. So we are saying that the length of $z$ is at most polynomially larger than the length of $x$. A general tip, since you will see $|\cdot|$ used for a variety of things in math, is to get used to parsing it as "size" rather than "absolute value", where the notion of size is context-dependent (sometimes absolute value!), and when it comes to strings it's usually length.

  3. Yes, it is limited to problems about whether a string belongs to a certain language. Hopefully, however, the material you are following has clarified that essentially any computational problem we know of can be posed in that framework. You want to find out whether there are 100 people who are all mutually friends on Facebook? This can be formulated as a problem on strings. The prime factorization of a number $n$? A problem on strings. Any problem that a computer (i.e., a Turing machine) can solve is a problem on strings. So this supposed limitation of the framework is not really restrictive. For a more philosophical discussion of whether truly all problems we could care about are problems over strings, you should probably refer to the Church-Turing thesis.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.