Games and Complexity in Graph Theory

1 / 10

Embed Share

Dive into the realm of games and complexity in graph theory, exploring topics such as Generalized Geography, Formula Game, and their implications in PSPACE completeness. Discover winning strategies, forced wins, and the intricacies of game theory applied to mathematical concepts.

keithley_k Follow

Uploaded on Mar 22, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

18.404/6.840 Lecture 19 Last time: - Review ??????DFA PSPACE - Savitch s Theorem: NSPACE ? ? - ???? is PSPACE-complete SPACE ?2? Today: (Sipser 8.3 8.4) - Games and Quantifiers - The Formula Game - Generalized Geography is PSPACE-complete - Logspace: L and NL

Games and Complexity Geography game Kalamazoo New York Kansas Boston Check-in 19.1 Let ? be the graph below. Which player has a winning strategy in the Generalized Geography game starting at node ?? (a) Player I (b) Player II (c) Neither player (d) Both players Oregon San Francisco Generalized Geography Game Played on any directed graph. Players take turns picking nodes that form a simple path. The first player stuck loses. Nebraska Arkansas Oklahoma ? = Assume two players: Player I and Player II Alaska ? ?,? Player I has a forced win in Defn: ?? = Generalized Geography on graph ? starting at node ?}. I Players take turns picking places that start with the letter which ended the previous place. No repeats allowed. The first player stuck (= cannot move) loses. forced win also called a winning strategy means that the player will win if both players play optimally. Theorem: ?? is PSPACE-complete Check-in 19.1

Games and Quantifiers ? The Formula Game Given QBF ? = ?1 ?2 ?3 / ?? There are two Players and . Player assigns values to the -quantified variables. Player assigns values to the -quantified variables. The players choose the values according to the order of the quantifiers in ?. Check-in 19.2 Which player has a winning strategy in the formula game on ? = ? ? ? ? ? ? (a) -player (b) -player (c) Neither player After all variables have been assigned values, we determine the winner: Player wins if the assignment satisfies ?. Player wins if not. Claim: Player has a forced win in the formula game on ? iff ? is TRUE. Therefore ? Player has a forced win on ?} = ????. Next: show ???? ???. Check-in 19.2

?? is PSPACE-complete Theorem: ?? is PSPACE-complete Proof: 1) ?? PSPACE (recursive algorithm, exercise) 2) ???? P?? Give reduction ? from ???? to ??. ? ? = ?,? Construct ? to mimic the formula game on ?. ? has Players I and II Player I plays role of -Player in ?. Ditto for Player II and the -Player. ? = ?1 ?2 ?3 / ?? ? assume in cnf ? =

Constructing the ?? graph ? Illustrate construction by example Say? = ?1 ?2 ?3 ?? [ ( ?1 ?2 ?3 ) (?1 ?2 ?4) ( ) ] ? = I = II = TRUE FALSE ? ? ?1 ?? ?2 ?1 Endgame should win if assignment satisfied all clauses should win if some unsatisfied clause ?2 ?1 ?1 ?? ?2 ?2 Implementation picks clause node claimed unsatisfied picks literal node claimed to satisfy the clause liar will be stuck ?4 ?3 ?1 ?2 ?1 ?1 ?1 ?2 ??

Log space To define sublinear space computation, do not count input as part of space used. Use 2-tape TM model with read-only input tape. Defn: L = SPACE log? NL = NSPACE log? read-only input tape does not count towards space used Log space can represent a constant number of pointers into the input. count cells used here read/write work tape Examples ? log? ?? ? } L 1. ababbaaaaaaaaaabbaba ???? NL 2. NL Work tape tracks corresponding locations in the input tape. Nondeterministically select the nodes of a path connecting ? to ?. L L = NL? Unsolved

Log space properties Theorem: L P Proof: Say ? decides ? in space ? log? . Defn: A configuration for ? on ? is ?,?1,?2,? where ? is a state, ?1 and ?2 are the tape head positions, and ? is the tape contents. The number of such configurations is ? ? ? log? ?? log ?= ?(??) for some ?. ?1 Therefore ? runs in polynomial time. Conclusion: ? P ? ?2 Theorem: NL SPACE log2? Proof: Savitch s theorem works for log space ?

NL properties Theorem: NL P Proof: Say NTM ? decides ? in space ? log? . Defn: The configuration graph ??,? for ? on ? has nodes: all configurations for ? on ? edges: edge from ?? ?? if ?? can yield ?? in 1 step. ??,? Check-in 19.3 We showed that ???? NL. What is the best we know about the deterministic space complexity of ????? (a) ???? PSPACE (b) ???? SPACE(?) (c) ???? SPACE log2? (d) ???? SPACE log ? ?start ?accept Claim: ? accepts ? iff the configuration graph ??,? has a path from ?start to ?accept ?? ?? Polynomial time algorithm ? for ?: ? = On input ? 1. Construct the ??,?. 2. Accept if there is a path from ?start to ?accept. Rejectif not. P NL L L = P? Unsolved Check-in 19.3