The Challenger-Solver game: Variations on the theme of P =?NP
- Yuri Gurevich
in Chapter in "Current Trends in Theoretical Computer Science", Eds. G. Rozenberg and A. Salomaa, World Scientific, Series in Computer Science
1989, Vol 40
Originally in Bulletin of the European Association for Theoretical Computer Science October 1989, 112-121. Reprinted in 1993 World Scientific book Current Trends in Theoretical Computer Science. (opens in new tab)pages 245-253
The question P=?NP is the focal point of much research in theoretical computer science. But is it the right question? We find it biased toward the positive answer. It is conceivable that the negative answer is established without providing much evidence for the difficulty of NP problems in practical terms. We argue in favor of an alternative to P=?NP based on the average-case complexity.