On the Approximation Method and the P versus NP Problem

Norbert Blum

First of all we give some reasons that "natural proofs" built not a barrier to prove P $\ne$ NP using Boolean complexity. Then we investigate the approximation method for its ext…