Трудно решаемые задачи и игра «Сапёр».

Abstract

In the paper it is shown based upon the theory of complexity of problems if a solving algorithm exists in a sample «Minesweeper» field, it has NP-complexity. Experimental treatments of the game show that the solving algorithm exists with certain probability. These results allow new classification of problems’ complexity to be proposed. Paper’s Appendix contains description of methods for evaluating results of players at the international Minesweeper championship.