Results 1 to 7 of 7

Math Help - Polynomial-time reduction (Probabilistic Automata)

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    16

    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 \Sigma_L = \{ 0,1 \} and \Sigma_I = \{ +, -, * \}. But now I'm not sure how to proceed. Please help!!
    Attached Thumbnails Attached Thumbnails Polynomial-time reduction (Probabilistic Automata)-equiv_reduction.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Polynomial-time reduction (Probabilistic Automata)

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2011
    Posts
    16

    Re: Polynomial-time reduction (Probabilistic Automata)

    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Polynomial-time reduction (Probabilistic Automata)

    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...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2011
    Posts
    16

    Re: Polynomial-time reduction (Probabilistic Automata)

    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. \sum_{q\in Q} f(q) = 1.
    Last edited by complexity9; December 7th 2011 at 11:46 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Polynomial-time reduction (Probabilistic Automata)

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Dec 2011
    Posts
    16

    Re: Polynomial-time reduction (Probabilistic Automata)

    Quote Originally Posted by Annatala View Post
    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..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Probabilistic Models
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: March 23rd 2011, 02:00 AM
  2. [SOLVED] Polynomial time/height
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: January 27th 2010, 10:48 AM
  3. Probabilistic Model
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: October 21st 2009, 12:04 AM
  4. I need help in this Probabilistic Model
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 18th 2009, 05:20 AM
  5. Replies: 0
    Last Post: March 9th 2008, 11:07 AM

Search Tags


/mathhelpforum @mathhelpforum