Является ли задача о половинном магическом квадрате NP-полной?

13

Вот проблема:

У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата.

Примеры:

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _ 
9 _ _  >>>  NO SOLUTION 
8 _ _

Эта проблема NP-полная? Если да, как я могу это доказать?

Кросспост на MS

levanovd
источник
2
Нет, просьба о помощи - это не плохо. Но ваш вопрос должен быть в рамках сайта, который вы задали. Я думаю, что Math SE подходит для этого вопроса, а TCS SE - нет.
Сянь-Чи Чанг 之 之
5
Мы принимаем вопросы о доказательстве NP-твердости, особенно когда проблема сложная. Например, рассмотрим три примера, перечисленные здесь в качестве ответов: meta.cstheory.stackexchange.com/questions/784/…
Суреш Венкат
6
Если это домашнее задание, мы не позволяем это, независимо от того, неэтично ли это.
Питер Шор
13
@levanovd: это не переполнение стека. У этого сообщества есть четкая политика, запрещающая домашние вопросы. Тот факт, что stackoverflow имеет другую политику, здесь не имеет значения.
Джефф
3
Я не знаю решения, и я не думаю, что это на уровне домашней работы. Однако я могу упустить что-то простое. Поэтому, если кто-то знает полное решение и считает этот вопрос домашним заданием, просто скажите. В то же время я предположу, что этот вопрос не домашнее задание и что тег [homework], использованный в Math SE, и предыдущий комментарий levanovd были просто ошибками.
Цуёси Ито

Ответы:

18

Заполнение частично заполненного латинского квадрата является NP-Complete. «Сложность заполнения неполных латинских квадратов» Чарльз Дж. Колборн. Дискретная прикладная математика, том 8, выпуск 1, апрель 1984 года, страницы 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1

Можно ли превратить проблему латинского квадрата в проблему магического квадрата с помощью модульной арифметики? Моя интуиция говорит, что да, но остальная часть моего мозга говорит: «Вернись к оценке!»

Питер Бут
источник
2
Было бы неплохо превратить это в строгий аргумент. Мне совсем не ясно, как модульная арифметика действительно поможет в сокращении завершения ЛАТИНСКОЙ ПЛОЩАДКИ до МАГИЧЕСКОЙ ПЛОЩАДИ, или наоборот. Было бы довольно красиво, если бы это можно было заставить работать.
Андрас Саламон
9

Этот вопрос состоит из двух частей: во-первых, проблема в NP, и во-вторых, сложность в NP?

Для первой части у меня есть положительный ответ с неочевидным доказательством. (Спасибо Сурешу за указание на более раннюю ошибку.)


Рассмотрим следующий способ формализации вопроса как решения проблемы:

НЕОГРАНИЧЕННОЕ ЗАВЕРШЕНИЕ ВОЛШЕБНОГО КВАДРАТА
Входные данные: положительное целое число заданное в унарном порядке, список целых чисел с их позициями в сетке n на n Вопрос: существуют ли целые числа для оставшихся позиций в сетке, так что расположение образует магический квадрат ?NNN

Если мы добавим ограничение, что каждое из целых чисел должно произойти ровно один раз в магическом квадрате, то результирующая проблема решения MAGIC SQUARE COMPLETION, очевидно, находится в NP. Определение магического квадрата в 1911 Британской энциклопедии , после Эйлера , имеет это ограничение; в отличие от этого, статья в Википедии в настоящее время использует терминологию «нормальный магический квадрат» и резервирует «магический квадрат» для неограниченной версии.1,2,...,N2

С по п сетке, по крайней мере , п число должно быть задано, в противном случае ответ тривиальный «YES» для неограниченной версии. Следовательно, можно предположить, что в этом случае размер входных данных требует более n бит. Для нормальной версии возможно, что есть входы, которые требуют нескольких битов, но не имеют решения; Чтобы избежать таких осложнений, я указал, что n дано в одинарном.NNNNN

Аргумент использует ограничение на возможный размер целых чисел, которые появляются в решениях. В нормальном случае эта оценка, очевидно, равна , но в общем случае априори не очевидно, что такая граница существует. Оказывается, существует экспоненциальная оценка.N2

Теорема ( Tyszka, теорема 12 ): любая система диофантовых уравнений, включающая уравнения вида и x i = x j + x k , для i , j , k { 1 , 2 , , n } , либо не имеет целочисленного решения или имеет решение, в котором каждый x i является целым числом и не более Иксязнак равно1Иксязнак равноИксJ+ИксКя,J,К{1,2,...,N}Иксяпо абсолютной величине.5N-1

Это также появилось как теорема 4.7 в:

2n2n1

xi=1xi=xj+xki,j,k{1,2,,n}xi2n

2n1

Это дает следующее:

N2O(N2)

O(N4)O(N8)n2+2(N+1)(N-2)+1знак равно3N2-2N-3N-2мО(м2)

N


Используя ограничение Пападимитриу на решения экземпляра INTEGER LINEAR PROGRAMMING, можно также показать, что версия, где все числа должны быть неотрицательными, также есть в NP.

Aр×sбр{-a,-a+1,...,a-1,a}, Тогда еслиAИксзнак равноб имеет решение в неотрицательных целых числах, оно также имеет решение, в котором каждый компонент находится в {0,1,...,s(рa)2р+1},

Ограничения, образующие магический квадрат, могут быть выражены в виде линейной программы с использованием aзнак равно1, с sзнак равноN2+1 переменные и рзнак равно2N+2неравенства. Это дает несколько большую границу, чем граница выше, где допустимы отрицательные числа, но сертификат по-прежнему имеет полиномиальный размер. (Спасибо Тони Тану за указание на результат Пападимитриу.)

  • Христос Х. Пападимитриу, О сложности целочисленного программирования , JACM 28 765–768, 1981. ( ссылка )
Андраш Саламон
источник
I guess I'm confused. if there's a poly bound on the size of the answers, then we are guaranteed to have a guess that can be read and verified in polynomial time.
Suresh Venkat
@Suresh: извиняюсь за ошибки, этот ответ оказалось сложнее записать, чем я ожидал.
Андрас Саламон