2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 NP сертификат
Сообщение05.04.2012, 18:56 


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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение05.04.2012, 19:24 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
max(Im) в сообщении #556671 писал(а):
Есть система уравнений из n уравнений и с константным числом неизвестных.

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

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

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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение05.04.2012, 19:54 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
 !  Профессор Снэйп, устное замечание за сквернословие

 Профиль  
                  
 
 Re: NP сертификат
Сообщение05.04.2012, 20:24 


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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение05.04.2012, 20:33 
Заморожен
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение06.04.2012, 07:42 


14/01/11
2916
max(Im) в сообщении #556707 писал(а):
А что делать в случае, когда вместо уравенений - неравенства?


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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение06.04.2012, 08:02 
Заморожен
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение06.04.2012, 09:29 


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


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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение06.04.2012, 09:46 


14/01/11
2916
max(Im) в сообщении #556903 писал(а):
Sender,
что значит $x_1 \to \max,$


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

Цитата:
почему $x_1$?


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

 Профиль  
                  
 
 Re: NP сертификат
Сообщение06.04.2012, 09:52 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group