# Prove that $P/poly$ is closed on $^*$.

Prove that $P/poly$ is closed on $^*$. Please help me with that because I cannot deal with that.

• Can you show that $P$ is closed under Kleene star? – Ariel Aug 23 '17 at 19:16
• Yes, my idea is: Let $L \in P$. Let $M$ recognizes $L$. If $M$ is going to accepting state, we can add additional edge to the initial state on every letter. – Logic Aug 23 '17 at 19:35
• This would create a non deterministic machine for $L^*$, and you need a deterministic one. Once you have the right idea on how to deterministically decide $L^*$ for $L\in P$, you can easily extend it to work for $L\in P/Poly$. – Ariel Aug 23 '17 at 19:42
• Oh, yeah. But, we can use dynamic programming to solve it. But, I cannot see what is difference in $P/poly$. After all, we treat a Turing machine from $P$ as blacbox. So, there is no difference- $P/poly$ machine is also blackbox. – Logic Aug 23 '17 at 19:50
• If $L\in P/Poly$, and you want to check if $x\in L$, then you need the advice for length $|x|$. Write down the dynamic programming solution and you'll see where it differs in the P/Poly case. – Ariel Aug 23 '17 at 19:55

## 3 Answers

Note that for $w\in\{0,1\}^n$ it holds that:

$w\in L^*\iff w\in L \lor \left(\exists i\in \{1,...,n-1\} : w_1...w_i\in L^* \land w_{i+1}...w_n\in L\right)$.

You can translate the above into a dynamic programming algorithm for deciding $L^*$. One way to do that is keeping an array $A[i]$, where $A[i]=1\iff w_1,...,w_i\in L^*$, and filling it from $i=0$ upwards. The running time $T(n)$ is bounded by $T(n)\le T(n-1)+T_L(n)$, where $T_L(n)$ is the time required for deciding membership to $L$ on inputs of length $n$. Hence, $T(n)\le nT_L(n)$, which is polynomial if $L\in P$.

This works fine if $L\in P$, however when $L\in P/Poly$, you have a polynomial time machine $M(x,y)$ and a sequence of advice $\{\alpha_n\}_{n\in\mathbb{N}}$, where $\alpha_n\in\{0,1\}^{p(n)}$ for some polynomial $p$, such that $x\in L \iff M\left(x,\alpha_{|x|}\right)=1$. The above procedure requires deciding membership to $L$ on inputs of length at most $n$. Thus, your advice for deciding $L^*$ on length $n$ inputs will be $\beta_n=\alpha_0,\alpha_1...,\alpha_n$ (which is still polynomial), and whenever you need to check membership to $L$ on a word $w$ of length $0\le i\le n$, execute $M(w,\alpha_i)$.

• Ok, you simply collect all advices into one big advice and use the same algorithm as for $P$. – Haskell Fun Aug 25 '17 at 15:54
• Exactly. Just need to make sure to feed the right advice to $M$ whenever you want to apply it to some input. – Ariel Aug 25 '17 at 17:07

To my eye, it is sufficient to show that there exists polynomial advice such that it recognize $L=M^*$, where $M\in P/Poly$.

It is obvious that such advice exists because we can split advices of particular words (recognizing by $M$) with symbol $\#$. Then, we have polynomial advice: $w_1\#w_2\#...\#w_n$, where $w_i$ is advice for some word recognizing by $M$. Polynomial machine for language $L$ can recognize it,simply launch $M$ on each $w_i$.

• The advice is fixed for the same length, there is no different advice for every word. Also, you're mixing the concepts of machine and language. – Ariel Aug 24 '17 at 22:33
• @Ariel, so advice is always the same ? – Haskell Fun Aug 24 '17 at 22:42
• The advice is the same for strings of the same length. I don't mean to discourage you, but you should probably not post answers to questions where you're not sure about the definitions of the objects involved. – Ariel Aug 24 '17 at 23:19

INPUT: $w=w_1..w_n$

for l = 1 to n
for i = 1 to n - 1
j = i + l - 1
if w_ij is accepted by M then A[i,j] = true
else
for k = i to j
if  A[i,k] and A[k+1,j] then A[i,j] = true

if A[1,n] then accept
else reject


Where w_ij is substring starting at $i$ and ending at $j$. $M$ is Turing machine recognized $L \in P/poly$. It work in polynomial time.

@Ariel, I don't see how it differs with algorithm for polynomial.

• I don't understand your solution, what is $A[i,j]$ supposed to be? Also, if $M$ is a Turing machine which takes advice, then it requires two parameters (the input and the advice), and you only give it $w_{ij}$ as input. – Ariel Aug 24 '17 at 22:36