P не равно NP?

[cartesius]

Буквально три дня назад была опубликовано доказательство одной 7 мат. задач тысячелетия (за ее доказательство институт Клея также предлагает миллион долларов): P=NP?

http://www.scribd.com/doc/35539144/pnp12pt

http://news.ycombinator.com/item?id=1586091

http://www.hpl.hp.com/personal/Vinay_Deolalikar/

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

Классы P и NP

В конечном счете проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?

Проще говоря, действительно ли задачу легче проверить, чем решить?

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

Это применимо ко всем подобным задачам, а не только к задаче о суммах подмножеств. Также это применимо к задачам, ответ на которые сложнее, чем ДА или НЕТ.

[править] Содержание проблемы

Диаграмма классов сложности при условии P ≠ NP.

Отношения между классами P и NP рассматриваются в теории вычислительной сложности (разделе теории вычислений), изучающей ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи).

[править] История

Из определения классов P и NP сразу вытекает следствие: P \= NP. Однако до сих пор ничего не известно о строгости этого включения, т. е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.

Впервые вопрос о равенстве классов был поставлен независимо Куком и Левиным (англ.) в 1971 году. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.

В настоящий момент проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

В августе 2010 года, американский исследователь Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.[1] Стивен Кук, один из пионеров теории вычислительной сложности, назвал его статью "относительно серьезной попыткой решения проблемы P vs NP".[2]

[Koreolan]

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

[cartesius]

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

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

Вроде серьезный ученый писал. И кроме использования мат. метода из стат. физики (неизвестно, насколько точно он доказан) пока придраться не к чему. В худшем случае задача сведется к строгому доказательству этого метода.

[Koreolan]

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

Вроде серьезный ученый писал. И кроме использования метода из стат. физики (неизвестно, насколько точно он доказан) пока придраться не к чему. В худшем случае задача сведется к строгому доказательству этого метода.

[vrammycowboy]

կուտա