Observations on Measure and Lowness for triangle open_2~P

摘要

Assuming that k>=2 and triangle open_k~P does not have p-measure 0, it is shown that BP centre dot triangle open_k~P = triangle open_k~P. This implies that the following conditions hold if triangle open_2~P does not have p-measure 0. (i) AM intersect co-AM is low for triangle open_2~P. (Thus BPP and the graph isomorphism problem are low for triangle open_2~P.) (ii) If triangle open_2~Pnot=PH, then NP does not have polynomial-size circuits.