74
правки
Изменения
Шапка доказательства
Для ''игры'' <math>\langle B_0,P_1,\dots,P_p \rangle</math>, ''последовательностью траекторий'' <math>\Sigma</math> является такая последовательность <math> B_0,\sigma_1,B_1,\dots,\sigma_p,B_p</math>, что для любого <math>i</math> траектория фигуры <math>P_i</math> на поле <math>B_{i-1}</math> приводит к полю <math>B_i</math>. Однако, если существует действие <math>\sigma_q</math> при некотором <math>q \leqslant p</math>, приводящее к проигрышу, то последовательность <math>\Sigma</math> завершается на <math>B_q</math>, а не на <math>B_p</math>.
==NP-полнота игры==
Рассмотрим следующую проблему, называемую '''k-cleared rows''' (<math>G,\Sigma</math>): в игре <math>G</math>, приводит ли <math>\Sigma</math> к освобождению хотя бы <math>k</math> рядов до проигрыша? Вспомним проблему 3-Partition, которая является NP-полной. Она звучит так: можно ли разбить заданное мультимножество целых чисел на тройки чисел так, чтобы у всех троек сумма была одинакова?
{{Теорема
|statement=
3-Partition сводится к k-cleared rows.
|proof =
}}
