In this paper, the authors mainly intend to clarify the relation between NP and PP . A randomized version of NP is given. Based on this equivalent definition of NP , another randomized complexity class is given: SUPER-NP . Although the SUPER-NP is very close to NP , but it is found surprisingly that PP?SUPER NP and thus NP?PP?SUPER-NP . In light of NP=PCP(log, O(1)) and the closeness of NP and SUPER-NP it is hoped that PP?PCP(log2,O(1)) conjecture can be peoved by showing that SUPER-NP?PCP(log2,O(1)).
[1] Garey, M.R., Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Complete. New York: W.H. Freeman and Company, 1979. 19~39.
[2] Hopcroft, J.E., Ullman, J.D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979. 285~320.
[3] Oded, Goldreich. Introduction to Complexity Theory. 1999. Available from http://www1.wisdom.weizmann.ac.il/~oded/ or http://theory.lcs.mit/~oded. 73~163.
[4] Papadimitriou, H. Computational Complexity. Addison-Wesley Publishing Company, 1994. 329~332.
[5] Gill, J. Computational complexity of probabilistic turing machines. SIAM Journal on Computing, 1977,6(4):675~695.
[6] Oded, Goldreich. Modern cryptography, probabilistic proofs and pseudorandomness. Algorithms and Combinatorics Series, Springer, 1998,17:31~73.
[7] Arora, S., Safra, S. Probabilistic checkable proofs: a new characterization of NP. JACM, 1998,45:70~122.