P ? NP Обсуждение, методы, мысли (Проблема перебора)

[arseniiv]

(Оффтоп)

Mihaylo в сообщении #1064264 писал(а):

А почему Вы привязались к полиномам вообще?

Потому что вы спрашивали именно про полиномиальную сложность. Не было бы полиномов — не было бы и её, например.

Mihaylo в сообщении #1064264 писал(а):

Ведь можно было сказать, почему некоторые алгоритмы быстрые/эффективные? Какие свойства у задач, решаемых быстро?

А почему-то все алгоритмы должны быть небыстрыми/неэффективными? Этому есть какая-то причина?

[Tot]

Nemiroff в сообщении #1061952 писал(а):

У Скотта Ааронсона было: конечно же $\mathrm{P\neq NP}$, и тут либо я прав, либо я бог — а меня устраивает и то, и другое.

Эх, ссылочку хорошо бы иметь, чтобы на стену в рамке повесить.

-- 19.01.2016, 22:11 --

На мой взгляд по данной проблеме слишком много теории, а с практикой совсем никак. В книгах можно найти преобразования нескольких NP-полных задач в другие. В статьях можно найти общую схему преобразования каждой новой NP-полной задачи к какой-то другой, помещённой в этот класс ранее.
Вот утверждается, что любая NP-полная задача сводится к любой другой за полиномиальное время с маленькой степенью. А как быть, если в задаче с $n$ переменными сама запись её имеет $2^n$ известных коэффициентов? Как преобразовать произвольную КНФ в сумму подмножества без дополнительных параметров? Или произвольный полином Жегалкина в ту же сумму подмножества? Преобразование $2^n$ однобитовых коэффициентов в $n$ многобитовых(достаточно $n$-битовых).
Что-то у меня этот момент не укладывается в голове. Подскажите, пожалуйста.

[svv]

Tot

Scott Aaronson в PHYS771 Lecture 9: Quantum писал(а):

Then there are only two possibilities: either I'm right, or else I'm a god! And either one sounds pretty good to me...

[Tot]

svv, благодарю за ссылку, повесил на стену. Не знал, что у Скотта Ааронсона курс лекций выложен в сети.
Приведённое высказывание ценно тем, что содержит потенциальную логическую ошибку, но доказать это можно лишь через доказательство исходного утверждения. Пока не доказано, нельзя исключить, что задача целочисленного линейного программирования по сложности имеет аналоги задачи линейного программирования. А там легко посчитать нельзя только в специальных задачах, которые конструируются сложно, а полиномиальные алгоритмы мало пригодны для вычислений.
В последние несколько лет мнение Скотта Ааронсона приводят при любом упоминании даже потенциального результата в теории сложности вычислений. Как-то странно. Нету что-ли никого больше? А у него даже на странице по приведённой ссылке Создатель упоминается 10 раз. Может и правда, что мир нельзя познать, а MIT нужно сделать синагогой?