The Challenger-Solver game: Variations on the theme of P =?NP
Yuri G. Gurevich · 1989
problem) X and Solver tries to solve them. Even if X has exponentially hard instances, Solver may have easy life: It may take exponential time to find a hard instance. ffl A: Are you saying that it is a priori possible that P 6= NP, but in practice NP problems are easy? ffl Q: Yes. I would like to see an alternative to P =?NP which is better balanced. If you prove it then programmers are happy, and if you disprove it then you have some real evidence that NP problems are hard. ffl A: If somebody discovers a decision algorithm for, say, SAT (the satisfiability problem for boolean formulas) which works in time n (ln ln n)=3 , will your programmers be happy? ffl Q: I am sure they would. I do not make a religion out of polynomial time. By the way, there are so many issues here: