Forum    Members    Search    FAQ

Board index » Your Things » Multimedia




Post new topic  Reply to topic  [ 1 post ] 
 
Author Message
 Post subject: Proof
 Post Posted: Thu Oct 22, 2009 3:10 pm 
User avatar
Offline
Joined: Sun Jul 12, 2009 4:23 am
Posts: 37
This is just a bogus proof for me to use in a conversation in the erfworld chat room about Parson's bracer. Everyone should feel free to ignore it. I figured this subforum was most appropriate since it IS fan created content. :-P

Input: An n by n othello board O, initialised to the start of the game, and two players W (white) and B (black).
Output: Does there exist a move Black can make such that he's guaranteed to win? True/false.
Assumptions: Let P=NP. Let Othello not have draws (draws don't require a fundamentally different algorithm but require more work than I want to put in to this). Resolve by having White automatically win draws, for simplicity.

Let B[i] be the machine that answers the question for Black; similarly, W[i] answers for white (does white have a move that guarantees a win?). Let i represent how many moves have occurred. Note that i cannot be larger than (n^2) - 4.
For all i, W[i] and B[i] have mirrored definitions in the obvious way.

Definition of B[j](O): If Black has already won, return true. If White has already won, return false. Otherwise,
nondeterministically guess the correct move to play, and play it, making board O'. Verify the move in polynomial time: W[j+1](O') will be false if the correct move was played, true if the incorrect move was played. Return true on
success, false on failure.

Since the total number of steps taken is O(n^2), and each step takes constant time by itself, the entire algorithm is O(n^2). Thus, we have just solved a PSPACE complete problem in polynomial time. Q.E.D. if P = NP then P = PSPACE.

  • Tip this post

    Make Anonymous
  • Top 
       
    Display posts from previous:  Sort by  
     
    Post new topic  Reply to topic  [ 1 post ] 

    Board index » Your Things » Multimedia


    Who is online

    Users browsing this forum: No registered users and 0 guests

     
     

     
    You cannot post new topics in this forum
    You cannot reply to topics in this forum
    You cannot edit your posts in this forum
    You cannot delete your posts in this forum
    You cannot post attachments in this forum

    Search for:
    Jump to: