Abstract
A general theorem on the complexity of a class of recognition problems is proved. As a particular case the following result is given: There is no algorithm which, for any 2-coloration of the infinite complete graph, can produce a monochromatic subgraph of
k vertices within
2
k
2
steps (at each step the color of an arbitrary edge is questioned).