0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Can you show that $P$ is closed under Kleene star? $\endgroup$ – Ariel Aug 23 '17 at 19:16
  • $\begingroup$ 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. $\endgroup$ – Logic Aug 23 '17 at 19:35
  • 2
    $\begingroup$ 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$. $\endgroup$ – Ariel Aug 23 '17 at 19:42
  • $\begingroup$ 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. $\endgroup$ – Logic Aug 23 '17 at 19:50
  • 2
    $\begingroup$ 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. $\endgroup$ – Ariel Aug 23 '17 at 19:55
1
$\begingroup$

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)$.

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

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ariel Aug 24 '17 at 22:33
  • $\begingroup$ @Ariel, so advice is always the same ? $\endgroup$ – Haskell Fun Aug 24 '17 at 22:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Ariel Aug 24 '17 at 23:19
-1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ariel Aug 24 '17 at 22:36

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.