Some combinatorial game problems require Ω( <i> n ^k </i> ) time

Abstract

The first "natural" languages are established as solvable m deterministic polynomial time, for the recogmtion of which polynomial-time lower bounds can be shown.