Изменения

Рассмотрим следующую проблему, называемую '''k-cleared rows''' (<math>G,\Sigma</math>): в игре <math>G</math>, приводит ли <math>\Sigma</math> к освобождению хотя бы <math>k</math> рядов до проигрыша? Вспомним проблему 3-Partition, которая является NP-полной. Она звучит такФормальное ее условие таково: ввод — последовательность целых чисел <math>a_1,a_2,\dots,a_{3s}</math> и неотрицательное число <math>T</math> такое, что <math>T/4 < a_i < T/2</math> для всех <math>1\leqslant i \leqslant 3s</math>, <tex>\sum_{i=1}^{3s} a_i = sT</tex>; вывод — можно ли <math>\{a_1,\dots,a_{3s}\}</math> разбить заданное мультимножество целых чисел на тройки чисел <math>s</math> непересекающихся подмножеств <math>A_1,\dots,A_s</math> так, чтобы у что для всех троек сумма была одинакова?<math>1\leqslant j \leqslant s</math> выполняется <tex>\sum_{a_i \in A_j} a_i = T</tex>.

|proof =  Опишем отображение из 3-Partition в k-cleared-rows. Для заданного ввода 3-Partition <math>P = \langle a_1,\dots,a_{3s},T \rangle</math>, составим игру <math>G(P)</math>, поле которой может быть полностью очищено, только если для <math>P</math> в задаче 3-Partition ответ положительный.[[Файл:board_partition.png|300px|thumb|right| Начальное игровое поле]]Начальное игровое поле содержит <math>s</math> ''контейнеров'', соответствующих множествам <math>A_1,\dots,A_s</math> в задаче 3-Partition. Последовательность фигур состоит из некоторого числа фигур, соответствующих каждому из <math>a_i</math> и подобранных так, что все фигуры для <math>a_i</math> должны быть помещены в один и тот же контейнер. Существует подходящее решение задачи 3-Partition для <math>\{a_1,\dots,a_{3s}\}</math> в том и только том случае, когда наборы фигур во всех контейнерах имеют одинаковую высоту. Последние три столбца в игровом поле представляют собой ''блок'', который не дает очистить ряды, пока не подойдет к концу последовательность фигур; если все контейнеры заполнены на одинаковую высоту, то все поле может быть очищено с помощью последней (специальной) части последовательности.Игра <math>G</math> состоит из следующих компонент: : '''Начальное игровое поле.''' Поле имеет <math>6T + 22 + (3s + O(1))</math> строк и <math>6s + 3</math> столбцов. Каждое <math>a_i</math> будет представлено <math>a_i + 1</math> блоками размером <math>6 \times 6 </math>; так как сумма элементов <math>A_j = \{a_i,a_j,a_k\}</math> равна <math>T</math>, получаем <math>6(T+3)=6T+18</math>. В дополнение к этим <math>6T+18</math> рядам, внизу находятся четыре ряда, обеспечивающие корректное положение блокам. Верхние <math>3s+O(1)</math> рядов (<math>O(1)</math> — это размер окрестности в модели вращения) изначально пусты и представляют собой промежуточную зону, где фигуру можно вращать и двигать, прежде чем она попадет в нижние <math>6T+22</math> рядов. Остальная часть поля может быть логически разделена на <math>s+1</math> части, где первые <math>s</math> частей имеют шесть клеток в ширину, а последняя — три клетки в ширину. Первые <math>s</math> частей — это контейнеры, имеющие следующий вид:# В первом и втором столбцах пусты все клетки, кроме нижних четырех.# Третий столбец не имеет занятых клеток.# В четвертом и пятом столбцах пусты только клетки в тех строках, чей номер по модулю 6 равен 5.# Шестой столбец не имеет пустых клеток. На {{Лемма|statement=Игра <math>G(P)</math> имеет полиномиальный размер от входных данных.|proof=}}