p-np

Очевидно

Какие ваши доказательства?

Я не говорил о том, что они есть, но это очевидная вещь, по- моему, нуждается ли она в доказательствах? Как белое - это белое? Надо ли что-то доказывать?

В том-то и суть, что надо.

Есть ли в массиве четное число? Проверка = O(n). // пробежались по массиву и посмотрели последний бит каждого числа.

В массиве есть число 6. Проверка = O(n). // пробежались по массиву и проверили есть ли число 6.

Это задачи одинаковой сложности = полиномиальной (даже линейной), т.е. в классе P.

А вот задача решения булевой формулы — NP-полная. Чтобы доказать, что решение есть или его нет, потребуется перебор «почти» всех комбинаций. Ответ 1 бит (решение есть, решения нет). Это NP-полная задача, т.е. любая другая NP задача может быть сведена к этой за полиномиальное время.

Фактически речь идет об экспоненциальном возрастании времени, необходимого для решения задачи. Ты формулируешь задачу с кодом длины N, а решение требует времени 2^N или 2^\sqrt(N) и т.д., главное, что больше любого многочлена p(N). Проверить такое решение, зная только бинарный ответ тоже не просто. Но если известна комбинация, то проверить ее правильность — линейное время.

Это очень интересный вопрос, похожий на «может ли Бог создать камень, который он не сможет поднять?» Если P!=NP, то, учитывая, что атомов в видимой части вселенной менее 10^81, можно сравнительно легко сформулировать задачу, и потратить на формулировку совсем немного бит, но для которой не будет существовать алгоритма решения за время существования вселенной, даже если бы в классический процессор были бы засуноты все атомы вселенной.

А есть еще всякие другие классы: PP, BP, BPP, QNP, QP и т.д. И вопросы отношения между ними тоже интересны.

что решение есть или его нет, потребуется перебор «почти» всех комбинаций

А разве нельзя это свести к простому линейному поиску? Можно смотреть на это с такой точки зрения: сначала мы генерируем массив из всех возможных значений (комбинаций), а затем точно также пробегаемся по этому массиву.

Размер этого массива получается 2^N и генерить его ты будешь соотв. 2^N времени.

Ну, начнем с того, что это очевидно для тебя, но не для машины

Но я по-прежнему не вижу принципиальной разницы. Массив и так может быть неограниченно большим.

А для машины разве есть что-нибудь «очевидное»? Пока еще ИИ не создали, если я не ошибаюсь. Машина — это груда железа. Когда она складывает 1+1, она не ведает, что творит.

Ну значит не судьба, сложность алгоритмов это не твое. Вперед клепать говнокод на пыхапэ!

Хорошо, но я хочу предпринять последнюю попытку. Вот, допустим, мы хотим перебрать все натуральные числа, и установить, есть ли «последнее число»? Это будет бесконечное вычисление, которое не даст никогда результата. Но реализация этого алгоритма тривиальна. Что тут вообще понимается под «сложностью» в таком случае? В чем заключается «сложность», как она формулируется хотя-бы?

А определение слабо прочитать?

Суть — сложность это время в «элементарных операциях», т.е. количество необходимых элементарных операций для гарантированного решения задачи при «любых начальных данных длины N».

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

Формально задачи ставятся в виде машины Тьюринга с заданным алфавитом. В этом случае длина ленты = длина начальных данных, а количество передвижений по ленте = затраченное время.

Суть — сложность это время в «элементарных операциях», т.е. количество необходимых элементарных операций для гарантированного решения задачи при «любых начальных данных длины N».

В таком случае, вырожденным случаем такой «сложности» будет бесконечная рекурсия, например, f=func(x){f(x)}

Вперед клепать говнокод на пыхапэ!

Кстати, не совсем понятно, причем тут похапэ, разве он по вычислительным возможностиям уступает машине Тьюринга? Тогда уж строгое ФП бери.

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

Опять ты? Объясняю на пальцах: есть три алгоритма, у одного сложность O(n), у второго O(n log n), у третьего O(n^2). Для некого набора данных они все отрабатывают за 1 минуту. Теперь представим, количество данных увеличили в 100 раз, тогда первый отработает за 1 ч 40 м, второй за 7 ч 40 м, третий за 6 д 22 ч 40 м. Всё это приблизительно, в реальности у алгоритмов могут быть разные константы, но нам важно оценить порядок роста, это и есть сложность.

А он все успешнее маскируется, угадал только по нику и комментам.

анонiмус тестит новый акк?

смешно говорить о равенстве

речь не о равенстве, а о эквивалентности в смысле [не]принадлежности к классу P(NP)

так... классы P и NP на пальцах:

Рассмотрим классы задач, для которых нужно лишь дать ответ «да» или «нет».

Представим себе самый обычный комп, но с бесконечной оперативной памятью. Класс P - это все задачи, для которых существует программа для этого компа, которая решает задачу за не очень большое время (время зависит как полином от объема входных данных).

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

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

Забанься уже сам, сучка.

Понятно, что компы, которые умеют форкаться, работают быстрее, чем компы, которые не умеют. Другое дело, что существует ли хоть одна задача, которую на обычных нельзя решить быстрее чем за время 2^n, но можно решить на форкающихся например за n^3.

Тем не менее, когда все компы закончат работу

А почему мы обязаны ждать, когда все компы закончат работу? Почему нельзя считать окончанием вычисления непосредственно нахождение результата хотя бы одним из компов? Тогда остальные ветки вычислений мы можем просто проигнорировать.

К сожалению, форкнувшиеся компы не имеют средств взаимодействия друг с другом.

А почему бы не дать им возможность общаться между собой (напрямую или через диспетчер)?

Я не могу врубится в сабж

Вся суть anonimous'а в 6 слов.

Ответ на все вопросы: потому что это иллюстрация недетерминированной машины Тьюринга, которая работает именно так.

тогда получается, что эта «теория» не имеет никакого отношения к реальным вычислениям? Например, если мы имеем неограниченное количество машин, которые могут форкнуть ветку вычислений и в случае успеха остановить вычисления, то ведь это же по-любому означает, что параллельность (которая Ъ, а не конкурентность) всегда поимеет линейный алгоритм?

реальным вычислениям

неограниченное количество машин

Ага

anonimous, уходи

А вообще, спасибо Вам большое за такое простое объяснение, я хоть нащупал немного нить, куда копать, остальные объяснения я вообще практически не понял:)

Ну, неограниченное кол-во можно заменить на ОЧЕНЬ большое, на МТ тоже лента бесконечная, так что не надо, мы о моделях же говорим.

Ок, только проблема в том, что в том месте, где в программе для НМТ ты делаешь недетерминированный переход, выполняющийся за 1 шаг, в реальной жизни нужно разослать K сообщений, где K запросто может быть O(2^N).

Pinkbyte

Не вся. Он не просто не может ни во что врубиться, он еще и считает чушью все, во что врубиться не может. А это уже следующая ступень деградации.

А почему мы обязаны ждать, когда все компы закончат работу? Почему нельзя считать окончанием вычисления непосредственно нахождение результата хотя бы одним из компов? Тогда остальные ветки вычислений мы можем просто проигнорировать.

А почему бы не дать им возможность общаться между собой (напрямую или через диспетчер)?

Потому что такое определение.

тогда получается, что эта «теория» не имеет никакого отношения к реальным вычислениям? Например, если мы имеем неограниченное количество машин, которые могут форкнуть ветку вычислений и в случае успеха остановить вычисления, то ведь это же по-любому означает, что параллельность (которая Ъ, а не конкурентность) всегда поимеет линейный алгоритм?

К реальным вычислениям эта теория имеет отношение такое, что для многих задач (поиск гамильтонова цикла, раскраска графа, выполнимость булевой функции итд) известнен «быстрый» алгоритм для таких форкающихся компов (а значит, это задачи из NP), но не известен алгоритм для нефоркающихся (а значит не понятно, P они или нет). И сколько бы не бились лучшие умы, никто не может для этих задач ни придумать быстрого алгритма, ни доказать, что его не существует.

Норм, каждый следующий ник делай с приставкой -101.