1
$\begingroup$

Definitions:

1. $$\mathsf{NP} = \{S \: \mid \: \text{Exists a polynomial, non-deterministic algorithm $A$ s.t. $A$ decides $S$} \}$$ Where a polynomial non-deterministic algorithm, is an algorithm that it's runtime is bounded by $p$ some polynomial, and may behave differently from run to run.

  1. $$\mathsf{P/poly} = \bigcup_{c=0}^\infty \mathsf{P/} n^c$$ We say a problem $S \in \mathsf{P}/l$ for some function $l\colon \mathbb{N} \rightarrow \mathbb{N}$, if there exists a polynomial algorithm A and an infinite set of strings $\{a_n\}_{n = 1}^\infty$ s.t.:

    a. $\forall n\colon \left | a_n \right | = l(n)$

    b. $\forall x\colon x \in S \Leftrightarrow A(a_{\left | x \right |},x) = 1$

Question:

Given $S \in \mathsf{P/poly}$, why is it not possible to show an algorithm $M$ that randomizes an advice string $a_{\left | x\right |}$ such that $\left | a_{\left | x\right |} \right | \leq p(\left | x \right |)$, and returns the output of $A(a_{\left | x\right |},x)$? Formally it should perform as follows:

  1. Set $a_{\left | x\right |}$ = ""

  2. While $\left | a_{\left | x\right |} \right | \leq p(\left | x \right |)$ choose non-deterministically:

    a. $a \leftarrow a0$

    b. $a \leftarrow a1$

    c. Continue to step 3

  3. Return $A(a_{\left | x\right |},x)$

I understand that $\mathsf{P/poly} \not \subseteq \mathsf{NP}$ because it contains non-decidable problems, but can't understand why this proof fails.

$\endgroup$

1 Answer 1

2
$\begingroup$

Consider the following functions with advice: $$ f(a,x) = a. $$ (The advice $a$ is one bit.)

The function $f$ is computable in polynomial time, and this shows that any language of the form $\{ x : |x| \in S \}$ belongs to $\mathsf{P/poly}$. If we choose $S$ to be some uncomputable set, then the corresponding language is not in $\mathsf{NP}$.

If you run your proposed algorithm on $f$, then you obtain a nondeterministic algorithm which accepts all strings. The problem is that $f$ is guaranteed to compute the language given the correct advice, but there is no guarantee as to what happens when it is fed the wrong advice.

$\endgroup$

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.