Thread: Polynomial-time reduction (Probabilistic Automata)

The problem that I'm having trouble with is the following (please see the attached image before proceeding).

Give a polynomial-time reduction of the equivalence problem for closed arithmetic sequential program to the equivalence problem for probabilistic automaton.

I have thought that maybe and . But now I'm not sure how to proceed. Please help!!

To solve this you need to assume you have a solution to the equivalence problem for sequential arithmetic. You need to describe an effective procedure for using this solution to answer "are these two probabilistic trees equivalent?".

You'll basically need to find a way to change any probabilistic tree into a unique (by equivalence) sequential arithmetic program, in polynomial time. That should be sufficient for the proof.

First note that we are talking about the equivalence of "closed" programs. This is much easier as the output to the closed program is an integer (always, no matter how many times you run it, since there is no input). The part I'm having trouble with is how one would encode a closed ASP (arithmetic sequential program) as a Probabilistic tree automaton.

Please help!

I'm not certain from what you're saying, but you may have things backwards (which is quite a common mistake with reductions). If you're reducing from ASPE to PTAE, you have to write a program that determines whether any two p-tree automata are equivalent by using a program that tells you if two arith-sequence programs are equivalent. The one you're reducing to is the one that you have to write; the one you reduce from is the one you're given.

So you need to tell if two PA trees are equivalent, by using a machine that tells you if two AS programs are equivalent. You need to describe a function that takes a PA tree and turns it into an arithmetic sequence program, and this function must preserve the equivalence of one to the other.

Look at how PA trees are evaluated. You want to describe how to turn each leaf into a sequence of one or more assignments (which should refer only to Dist(Q) and constants), and how to turn an internal node into a sequence of one or more assignments (which will refer only to the variables that come from each branch, whether leaf or internal). Since I'm not 100% certain what Dist() signifies I can't take this all the way, but it should be straightforward...

Oh sorry about that, Dist(Q) is the set of probability distributions on the set of states Q, that is, the set of functions f:Q->[0,1] s.t. .

I'm so sorry. I got this backwards, just like I warned you about. :P You are building the thing you reduce from, not the other way around. I was making an error when I said "reduce to the halting problem" in another post.

The other way is impossible, which is how I figured this out. This way is doable. You have a solver for "do these trees give the same result", and you want to build a solver for "do these sequences of addition, subtraction, and multiplication give the same result". To do this, you need to turn each sequence into a tree.

I'll respond more later, can't finish this now.

Originally Posted by Annatala

I'm so sorry. I got this backwards, just like I warned you about. :P You are building the thing you reduce from, not the other way around. I was making an error when I said "reduce to the halting problem" in another post.

The other way is impossible, which is how I figured this out. This way is doable. You have a solver for "do these trees give the same result", and you want to build a solver for "do these sequences of addition, subtraction, and multiplication give the same result". To do this, you need to turn each sequence into a tree.

I'll respond more later, can't finish this now.

Hi Annatala, would it be possible if you try to help me do this question now? I've been trying to find this polynomial time reduction, but I find it quite hard and unable to do it.

Thanks alot! I reallly appreciate it..