NP сертификат

[max(Im)]

Есть система уравнений из n уравнений и с константным числом неизвестных. И рассматривается задача -- правда ли, что она несовместна? Как показать, что задача из NP? То есть что можно дать человеку, чтобы он за полиномиальное время проверил, что она действительно несовместна?
В случае совместности достаточно дать решение... А тут неясно...

[Профессор Снэйп]

max(Im) в сообщении #556671 писал(а):

Есть система уравнений из n уравнений и с константным числом неизвестных.

А уравнения какого сорта? Линейные? Алгебраические (с многочленами)? Или ваще дифференциальные?

Если алгебраические, то уже для одного уравнения задача просто алгоритмически неразрешима. См. сюда, однако Какое там, в задницу, NP...

А если линейные... коэффициенты откуда? Из $\mathbb{Z}$, надо полагать (впрочем, можно и из $\mathbb{Q}$, совершенно неважно). Ежели так, то всё просто. Сертификат должен демонстрировать, что ранг расширенной матрицы больше ранга матрицы коэффициентов при переменных. Выглядит как набор из $n$ чисел, на которые надо последовательно умножать строки и затем их складывать. Если при такой линейной комбинации коэффициенты при переменных занулятся, а свободные члены нет, то система несовместна.

[PAV]

Профессор Снэйп, устное замечание за сквернословие

[max(Im)]

Да, коэффициенты целые, а уравнения линейные.
Спасибо, действительно, очевидно...
А что делать в случае, когда вместо уравенений - неравенства?

[Профессор Снэйп]

Кстати, по поводу уравнений. Систему ведь можно тупо методом Гаусса решать, а это полиномиальный алгоритм. И если система несовместна, то по ходу Гаусса этот факт всплывёт. То есть совместность/несовместность оказываются не просто NP-свойствами, а даже полиномиальными свойствами.

-- Чт апр 05, 2012 23:36:20 --

С неравенствами, думаю, тоже просто. Мне кажется, что там тоже должна быть полиномиальность, хотя детали с ходу пока не вырисовываются.

[Sender]

max(Im) в сообщении #556707 писал(а):

А что делать в случае, когда вместо уравенений - неравенства?

За полиномиальное время можно решить задачу линейной оптимизации $x_1 \rightarrow \max$.

[Профессор Снэйп]

Я, кстати, вчера, уже засыпая, понял, что не выяснил одной важной вещи. Коэффициенты у уравнений целочисленные, а сами решения тоже целочисленными должны быть? Или допускаются произвольные рациональные?

Потому что если под совместностью системы понимать существование целочисленных решений, то предложенный алгоритм не годится.

С неравенствами тот же вопрос.

[max(Im)]

Решения могут быть произвольными. Но говорят, что и в случае целочисленных $x_i$ тоже NP.


Sender,
что значит $x_1 \to \max,$ почему $x_1$?

[Sender]

max(Im) в сообщении #556903 писал(а):

Sender,
что значит $x_1 \to \max,$

А слова "задача линейной оптимизации" вас не смущают?

Цитата:

почему $x_1$?

Например, потому, что $x_1$ заведомо присутствует в системе, если, конечно, не рассматривать системы вовсе без неизвестных.

[max(Im)]

Хорошо, пусть будет линейная оптимизация. Для нее мне известен лишь симплекс-метод (который экспоненциален в общем случае). Да, есть полиномиальные алгоритмы. Но хотелось бы опираться на что-то известное...