Вот проблема:
У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата.
Примеры:
2 _ 6 2 7 6
_ 5 1 >>> 9 5 1
4 3 _ 4 3 8
7 _ _
9 _ _ >>> NO SOLUTION
8 _ _
Эта проблема NP-полная? Если да, как я могу это доказать?
cc.complexity-theory
np-hardness
np
puzzles
levanovd
источник
источник
Ответы:
Заполнение частично заполненного латинского квадрата является NP-Complete. «Сложность заполнения неполных латинских квадратов» Чарльз Дж. Колборн. Дискретная прикладная математика, том 8, выпуск 1, апрель 1984 года, страницы 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1
Можно ли превратить проблему латинского квадрата в проблему магического квадрата с помощью модульной арифметики? Моя интуиция говорит, что да, но остальная часть моего мозга говорит: «Вернись к оценке!»
источник
Этот вопрос состоит из двух частей: во-первых, проблема в NP, и во-вторых, сложность в NP?
Для первой части у меня есть положительный ответ с неочевидным доказательством. (Спасибо Сурешу за указание на более раннюю ошибку.)
Рассмотрим следующий способ формализации вопроса как решения проблемы:
Если мы добавим ограничение, что каждое из целых чисел должно произойти ровно один раз в магическом квадрате, то результирующая проблема решения MAGIC SQUARE COMPLETION, очевидно, находится в NP. Определение магического квадрата в 1911 Британской энциклопедии , после Эйлера , имеет это ограничение; в отличие от этого, статья в Википедии в настоящее время использует терминологию «нормальный магический квадрат» и резервирует «магический квадрат» для неограниченной версии.1 , 2 , … , n2
С по п сетке, по крайней мере , п число должно быть задано, в противном случае ответ тривиальный «YES» для неограниченной версии. Следовательно, можно предположить, что в этом случае размер входных данных требует более n бит. Для нормальной версии возможно, что есть входы, которые требуют нескольких битов, но не имеют решения; Чтобы избежать таких осложнений, я указал, что n дано в одинарном.N N N N N
Аргумент использует ограничение на возможный размер целых чисел, которые появляются в решениях. В нормальном случае эта оценка, очевидно, равна , но в общем случае априори не очевидно, что такая граница существует. Оказывается, существует экспоненциальная оценка.N2
Это также появилось как теорема 4.7 в:
Это дает следующее:
Используя ограничение Пападимитриу на решения экземпляра INTEGER LINEAR PROGRAMMING, можно также показать, что версия, где все числа должны быть неотрицательными, также есть в NP.
Ограничения, образующие магический квадрат, могут быть выражены в виде линейной программы с использованиема = 1 , с s = n2+ 1 переменные и г = 2 н + 2 неравенства. Это дает несколько большую границу, чем граница выше, где допустимы отрицательные числа, но сертификат по-прежнему имеет полиномиальный размер. (Спасибо Тони Тану за указание на результат Пападимитриу.)
источник