# Why can't you randomize an advice string to show that $P/poly \subseteq NP$

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.

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.