A k-query oracle Turing machine is an oracle Turing machine that is permitted to make at most k queries on each input. A k-query oracle Turing machine M with an oracle for A is written M^A,k. Define P^A,k to be the collection of languages that are decidable by polynomial time k-query oracle Turing machines with an oracle for A.

a. Show that NP ∪ coNP ⊆ PSAT,1.

b. Assume that NP ≠ coNP. Show that NP ∪ coNP ⊊ P^SAT,1.