Computing a perfect strategy for n × n chess requires time exponential in n.

scientific article (publication date: September 1981)