Что за задача Пи против нПи?

[grim2d]

В сериале "Элементарно" говорится об этом, что это такое? Google не помог(
Я школьник и поэтому прощу объяснить проще.

[VAL]

grim2d в сообщении #797000 писал(а):

В сериале "Элементарно" говорится об этом, что это такое? Google не помог(
Я школьник и поэтому прощу объяснить проще.

Переведите на английский.
Примерно так: P vs NP
Или даже так: P=NP
И снова обратитесь за помощью к Google

[gris]

Это в сериале "числа" в первых эпизодах. Собственно, к числу $\pi$ не имеет отношения. Происходит от слова полиномиальный. В общем, о сложных алгоритмах.

[Xaositect]

grim2d в сообщении #797000 писал(а):

Я школьник и поэтому прощу объяснить проще.

Попробую объясить.

Вот представьте себе, что у нас есть уравнение с большим количеством переменных, но по условию они могут принимать значение $0$ или $1$. Тогда для того, чтобы узнать, является ли какой-то набор значений переменных решением, можно просто подставить их и проверить. Это делается быстро. А вот найти какое-нибудь решение значительно сложнее: самый простой способ - это просто перебирать значения переменных и проверять. Но если переменных много, то возможных подстановок очень много (1 переменная - 2 значения, 2 переменных - 4 значения, 3 - 8, 4 - 16 и т.д.), поэтому нахождение решений получается очень медленное.

Так вот, очень грубо говоря, проблема $\mathbf{P}\neq \mathbf{NP}$ состоит в том, чтобы либо доказать, что найти решения нельзя быстро, либо найти быстрый способ. Большинство специалистов считает, что, скорее всего, быстрого способа нет.

$\mathbf{P}\neq \mathbf{NP}$ связана не только с этой задачей. Очень многие задачи можно решать перебором, и некоторые из них эквивалентны решению $0-1$-уравнений, то есть если мы найдем способ быстро решать уравнения, мы сможем быстро решать другие переборные задачи, и наоборот.

[venco]

Чуть подробнее.

Сначала о полиномиальности - если время на некоторую обработку данных переменного размера зависит от этого размера, как полином какой-то степени - квадрат, или куб, например, то сложность этой обработки называют полиномиальной. Может быть и гораздо медленнее, например, экспоненциальное время, когда оно равно, к примеру - $2^N$, где $N$ - размер данных. (Есть и ещё хуже варианты, но это уже детали.)

Так вот, все задачи, для решения которых есть полиномиальный алгоритм решения относятся к классу $\mathbf{P}$ - polynomial. Примеры таких задач - сортировка, решение системы линейных уравнений, умножение больших чисел.

Есть ещё класс задач, для которых такого алгоритма не известно, но есть хотя бы возможность за полиномиальное время проверить, что решение является именно решением, т.е. если мы каким либо образом быстро угадаем решение, то значит решим задачу за полиномиальное время, т.к. проверка полиномиальна. Такой класс задач назвали $\mathbf{NP}$ - non-determenistic polynomial - негарантированно полиномиальные. Пример такой задачи привёл Xaositect, ещё один пример - разложение на множители большого числа.

Итак, если для таких задач удастся придумать быстрый угадыватель, то эти задачи также окажутся полиномиальными, т.е. окажется $\mathbf{NP}= \mathbf{P}$. А если не удастся, то $\mathbf{NP}\neq \mathbf{P}$.
Вот это и есть главный вопрос теории алгоритмов.

[svv]

Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?

Или, может быть, для остальных $\mathbf{NP}$-задач лишь станет известно, что такие алгоритмы существуют, только их ещё найти надо?

[Urnwestek]

svv в сообщении #797043 писал(а):

Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?

Это верно лишь для $\mathbf{NP}$- полных.

[Xaositect]

svv в сообщении #797043 писал(а):

Правильно ли я понял, что есть какая-то такая $\mathbf{NP}$-задача, что если для нее мы найдем полиномиальный алгоритм решения, то и все другие $\mathbf{NP}$-задачи сразу станет возможным тоже решать за полиномиальное время?

Если найдется полиномиальный алгоритм для одной $\mathbf{NP}$-полной задачи, то для всех задач из $\mathbf{NP}$ алгоритм сразу строится по сводимости или по проверяющей машине (правда, степень при $n$ может сильно увеличиться, но все равно все будет полиномиально)

[venco]

Есть группа $\mathbf{NP}$-задач, к которым можно свести все $\mathbf{NP}$-задачи - $\mathbf{NP-complete}$. Если для какой-то из них будет найдено полиномиальное решение, то это докажет, что $\mathbf{P}=\mathbf{NP}$. И наоборот, если докажут, что $\mathbf{P}\neq\mathbf{NP}$, то значит для $\mathbf{NP-complete}$ задач полиномиального решения нет.

[svv]

А, интересно, встречались уже задачи, про которые сначала думали, что они из класса $\mathbf{NP}$ (не полные), а потом для них неожиданно находился полиномиальный алгоритм?

[Urnwestek]

svv в сообщении #797053 писал(а):

А, интересно, встречались уже задачи, про которые сначала думали, что они из класса $\mathbf{NP}$ (не полные), а потом для них неожиданно находился полиномиальный алгоритм?

Если для задачи существует полиномиальный алгоритм, то она лежит в классе $\mathbf{NP}$.

[svv]

Я имел в виду, были ли задачи, для которых позже оказалось, что их не только проверять, но и решать можно за полиномиальное время, и они на самом деле принадлежат классу $\mathbf{P}$?

[venco]

Проверка простоты числа. Сначала думали что оно вообще не в $\mathbf{NP}$, потом нашли сертификат простоты, который можно проверить полиномиально, т.е. оказалось в $\mathbf{NP}$, а не очень давно нашли и полностью полиномиальный алгоритм.

[svv]

Спасибо. Тогда и надежда на $\mathbf{P}=\mathbf{NP}$ есть.

[VAL]

svv в сообщении #797058 писал(а):

Спасибо. Тогда и надежда на $\mathbf{P}=\mathbf{NP}$ есть.

Надежда, может, и есть. А вот алгоритма решения NP-полных задач за полиномиальное время - нет