Algorithms Lecture 33 Announcements Final exam At official scheduled time Dec 21 8 10am Students with accommodations start at 8am and email me your scanned exam by your allotted time Let me know if you need to make other arrangements To be submitted via Gradescope Open book open notes Comprehensive but will focus on material since the midterm Beyond NP PSPACE PSPACE Allows us to focus on space complexity rather than time complexity An example of a class beyond NP There are problems arising in practice that are in PSPACE Complexity classes P problems that can be solved efficiently i e in polynomial time NP problems where existence of a correct solution can be verified efficiently coNP problems where non existence of a solution can be PSPACE problems that can be solved using polynomial verified efficiently space P NP PSPACE We believe all inclusions are strict though we can t yet prove it P PSPACE Proof an algorithm that runs in polynomial time can use only polynomial space Note an algorithm that uses polynomial space might use exponential time or even unbounded time NP PSPACE Fix some L NP We know there is a poly time verifier V such that x L w V x w 1 w poly x Define the following algorithm A x exhaustively search for w such that V x w 1 A can be implemented using polynomial space Reductions Can still talk about reductions like before L is poly time reducible to L if there is a function f that can be computed in polynomial time such that x L iff f x L If L is reducible to L and L PSPACE then L PSPACE PSPACE completeness The hardest problems in PSPACE Defined analogously to NP completeness L is PSPACE complete if L PSPACE and every L PSPACE is reducible to L QSAT QSAT Given a Boolean formula on n variables determine whether x1 x2 x3 x1 xn 1 Note SAT asks if x1 x2 x3 x1 xn 1 SAT is trivially reducible to QSAT QSAT is not believed to be in NP How would you verify that a QSAT formula is true QSAT PSPACE Use a recursive algorithm A If x1 x2 x1 xn Output A x2 0 xn A x2 1 xn If x1 x2 x1 xn Output A x2 0 xn A x2 1 xn Base cases are trivial What is the complexity of this algorithm
View Full Document
Unlocking...