В работе на основании теории сложности задач показано, что если алгоритм раскрытия некоторого поля игры «Сапёр» существует, то он имеет сложность NP. Результаты экспериментального исследования игры показали, что алгоритм раскрытия существует с некоторой вероятностью. Этот факт позволяет предложить новую классификацию сложности задач. В приложении приводится описание методов оценки результатов в международных спортивных соревнованиях по игре в «Сапёр».

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.