2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 p-np
Сообщение18.10.2014, 09:16 


18/10/14

11
Я не могу врубится в сабж. Если исходить из этого вот примера из википедии
Цитата:
Например, верно ли, что среди чисел −2, −3, 15, 14, 7, −10, … есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

Разница между p и np эквивалентна разнице между ответами на вопросы (решениями) "Есть ли вхождение X в множество" и "Есть ли взождения X и какие именно -- т.е. найти их все" Очевидно, что это не эквивалентные вычислительные задачи, смешно говорить о равенстве. Кажется, я неправильно понимаю проблему, либо пример некорректен. Объясните пожалуйста на пальцах, в чем тут подвох.

 !  Повторная регистрация заблокированного участника. Заблокирован.
/ GAA, 18.10.2014

 Профиль  
                  
 
 Re: p-np
Сообщение18.10.2014, 12:53 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Не читайте википедию. Читайте, например, Гэри, Джонсон "Вычислительные машины и труднорешаемые задачи". Или Голдрайха "Computational Complexity: A Conceptual Perspective" по-английски.

Разница между P и NP как между "Верно ли, что данное подмножество суммируется в 0?" и "Верно ли, что какое-то подмножество суммируется в 0?"

 Профиль  
                  
 
 Re: p-np
Сообщение18.10.2014, 15:13 
Заслуженный участник
Аватара пользователя


11/03/08
9489
Москва
Приведенный Вами пример это не две задачи, одна из которых P, другая NP. Это пояснение, что такое класс NP. К классу P относятся задачи, решаемые за полиномиальное время. Есть задачи, для которых невозможность решить за полиномиальное время доказывается. Однако есть достаточно большой набор задач, некоторые из которых имеют важное прикладное значение, для которых полиномиальный алгоритм решения неизвестен, но проверить, что это решение, можно за полиномиальное время. Это позволяет надеяться, что существует и полиномиальный алгоритм их решения, и мы его просто ещё не придумали. В этом случае получится P=NP. Но возможно, что удастся доказать, что такой алгоритм невозможен. Тогда $P\neq NP$

 Профиль  
                  
 
 Re: p-np
Сообщение08.01.2017, 23:07 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Данная информация по теме может быть полезна интересующимся (не нашёл лучшего места на форуме, чтобы её оставить):
В этой записи у AVVA-жж ссылки на обзор по теме от Скотта Ааронсона (англ.). Там два варианта обзора -- для специалистов и для гумманитариев. Но оба не для слабонервных :)

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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