lenge (RGC): building a robot that aces exams! Each team is comprised of n students led by a professor. k topic areas of EECS are critical to the competition. For each topic area, a student is either an expert in that area or not. It is guaranteed that Teaml led by Profl will succeed if it includes at least one student expert from each of the k topic areas (irrespective of what Team2 does). Otherwise, Team2 (led by Prof2) will win The professors select their teams from 2n students as follows. First, the students are arbi trarily organized into an ordered sequence of pairs Pi, P2... .P Profl starts by picking one student from P1 (the other goes to Team2), then Prof2 picks a student from P2 (with the other going to Teaml) and so on, until each student has been allocated to some team. Consider the problem RGC1 defined below: RGC(P1, P2., P) Teaml has a winning strategy for the ordered sequence of student pairs P, P2, , Pa Here each P denotes a student pair with their associated topics(Gubject areas). Show that RGCl is PSPACE-complete. Hint: Use a reduction from TQBF. Don't forget to show that RGCl is in PSPACE You can assume the following definition of TQBF: TQBF {(d) | ? is a true fully quantified Boolean formula of the form lenge (RGC): building a robot that aces exams! Each team is comprised of n students led by a professor. k topic areas of EECS are critical to the competition. For each topic area, a student is either an expert in that area or not. It is guaranteed that Teaml led by Profl will succeed if it includes at least one student expert from each of the k topic areas (irrespective of what Team2 does). Otherwise, Team2 (led by Prof2) will win The professors select their teams from 2n students as follows. First, the students are arbi trarily organized into an ordered sequence of pairs Pi, P2... .P Profl starts by picking one student from P1 (the other goes to Team2), then Prof2 picks a student from P2 (with the other going to Teaml) and so on, until each student has been allocated to some team. Consider the problem RGC1 defined below: RGC(P1, P2., P) Teaml has a winning strategy for the ordered sequence of student pairs P, P2, , Pa Here each P denotes a student pair with their associated topics(Gubject areas). Show that RGCl is PSPACE-complete. Hint: Use a reduction from TQBF. Don't forget to show that RGCl is in PSPACE You can assume the following definition of TQBF: TQBF {(d) | ? is a true fully quantified Boolean formula of the form
