Separating <em>PH</em> from <em>PP</em> by Relativization<sup>1</sup>
Acta Mathematica Sinica, English Series
Acta Mathematica Sinica,
Chinese Series
Adv Search »  
Acta Mathematica Sinica, English Series  1992, Vol. 8 Issue (3): 329-336    DOI: 10.1007/BF02582920
articles Current Issue | Next Issue | Archive | Adv Search  |   
Separating PH from PP by Relativization1
Fu Bin1,2
1. Computer Science Department Beijing Computer Institute, 100044, Beijing, China
2. Beijing Laboratory of Cognitive Science University of Science and Technology of China, Beijing, China
 Download: PDF (2350 KB)   HTML (0 KB)   Export: BibTeX | EndNote (RIS)      Supporting Info
Abstract We construct an oracle A such that .So the polynomial time hierarchy is separated from the polynomial time probabilistic complexity class in relativization.
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
Articles by authors
Fu Bin
Key words:   
Received: 1990-08-12;
Fund: 1 This research is supported in part by HTP863.
Cite this article:   
Fu Bin. Separating PH from PP by Relativization1[J]. Acta Mathematica Sinica, English Series, 1992, 8(3): 329-336.
URL:      or
[1] Beigel,R.,Polynomial interpolation,threshold circuits,and the polynomial hierarchy,Manuscript,1990.
[2] Beigel,R.Hemachandra,L.A.and Wechsung,G.,On the power of probabilistic polynomial time,In proceeding of 4th annual conference on structural complexity theory,225-227,June 1989.
[3] Minsky,M.L.and Papert,S.A.,Perceptrons,MIT Press,Cambridge,MA,1988.
[4] Papadimitriou,C.H.and Zachos,S.K.,Two remarks on the complexity of counting,In the proceeding of the 6th GI conference of theoretical computer science,269-276,Springer-Verlag,1983.
[5] Schöning,U.Kober,J.Toda,S.and Toran,J.,Turing maachines with few accepting computation and low sets for PP,In proceeding of 4th annual conference on structural complexity theory,208-215,June 1989.
[6] Toda,S.,On The computational power of PP and ?P,In proceedings of the 30th IEEE symposium on foundations of computer science,514-519,1989.
[7] Wagner,K.W.,The complexity of combinatorial problems with succint input representation,Acta Informatica,23(1986),325-356.
No Similar of article
  Copyright 2012 © Editorial Office of Acta Mathematica Sinica