A small note on progress made to improve the Karp-Lipton Theorem
The original Karp-Lipton theorem says that
If NP is contained in P/poly or if NP has polynomial sized circuits then polynomial hierarchy collapses to its second level.
This was further improved upon by Kobler and Watanabe. They showed that polynomial hierarchy collapses down to ZPP^NP.
The class S2P was defined by Canetti and studied by Russell and Sundaram. Russell and Sundaram observed that S2P contains P^NP and MA. It is very easy to observe that S2P is contained in Sigma2P and Pi2P. Cai proved a fundamental containment result that S2P is contained in ZPP^NP. (i.e. there is a zero error poly time oracle machine asking queries to a SAT oracle that can accept S2P.) Samik Sengupta observed that if NP is contained in P/poly then polynomial hierarchy collapses to S2P. There by, a nice improvement over Karp-Lipton arose from the class S2P.
Before this result came, Arvind and Kobler proved that if NP has polysized circuits then MA=AM. What is known unconditianally is that MA is contained in AM. To prove that AM is contained in MA, the fact that SAT can be expressed as a polysized circuit (using assumption that NP has polysized circuits) is the key. In fact, the same idea was used by Sengupta to observe the above mentioned improvement on Karp-Lipton.
Recently, (STACS 2008) Chakravarthy and Roy show that S2P is contained in P^prAM. They formally define this class and show that it is contained in ZPP^NP. Hence, S2P contained in P^prAM contained in ZPP^NP, an improvement over upper bound for S2P given by Cai. It is an important open problem to show that if NP has polynomial sized circuits then PH collapses to MA. No such result has been studied in literature. This recent paper (Chakravarthy Roy) however shows that PH collapses to P^prMA. This is the first proof in this spirit. But the essence of the proof is exactly same as Arvind and Kobler's proof.
"Underlying useful assumption that one can get a polysized circuit for SAT."
The original Karp-Lipton theorem says that
If NP is contained in P/poly or if NP has polynomial sized circuits then polynomial hierarchy collapses to its second level.
This was further improved upon by Kobler and Watanabe. They showed that polynomial hierarchy collapses down to ZPP^NP.
The class S2P was defined by Canetti and studied by Russell and Sundaram. Russell and Sundaram observed that S2P contains P^NP and MA. It is very easy to observe that S2P is contained in Sigma2P and Pi2P. Cai proved a fundamental containment result that S2P is contained in ZPP^NP. (i.e. there is a zero error poly time oracle machine asking queries to a SAT oracle that can accept S2P.) Samik Sengupta observed that if NP is contained in P/poly then polynomial hierarchy collapses to S2P. There by, a nice improvement over Karp-Lipton arose from the class S2P.
Before this result came, Arvind and Kobler proved that if NP has polysized circuits then MA=AM. What is known unconditianally is that MA is contained in AM. To prove that AM is contained in MA, the fact that SAT can be expressed as a polysized circuit (using assumption that NP has polysized circuits) is the key. In fact, the same idea was used by Sengupta to observe the above mentioned improvement on Karp-Lipton.
Recently, (STACS 2008) Chakravarthy and Roy show that S2P is contained in P^prAM. They formally define this class and show that it is contained in ZPP^NP. Hence, S2P contained in P^prAM contained in ZPP^NP, an improvement over upper bound for S2P given by Cai. It is an important open problem to show that if NP has polynomial sized circuits then PH collapses to MA. No such result has been studied in literature. This recent paper (Chakravarthy Roy) however shows that PH collapses to P^prMA. This is the first proof in this spirit. But the essence of the proof is exactly same as Arvind and Kobler's proof.
"Underlying useful assumption that one can get a polysized circuit for SAT."
Comments
:P