Proof

Movies, songs, or whatever other stuff you have created.

Proof

Postby quindraco » Thu Oct 22, 2009 3:10 pm

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.
User avatar
quindraco
 
Posts: 34
Joined: Sun Jul 12, 2009 4:23 am

Return to Multimedia

Who is online

Users browsing this forum: No registered users and 1 guest