In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time

Submitted by smcneil on Mon, 2012-01-16 00:00
Author: 
R. Impagliazzo
V. Kabanets
A. Wigderson
Publication: 
Journal of Computer Systems and Sciences (JCSS), vol. 65, no. 4, pp. 672-694, 2002.
Conference on Computational Complexity, pp. 2-12, 2001.
Year: 
2001
Abstract: 
http://www.math.ias.edu/~avi/PUBLICATIONS/ABSTRACT/ikw02.pdf
Files
File: 
Journal version (pdf)
Journal version (ps)
bibTeX