Задача тысячелетия - Равенство классов P и NP

Равенство классов P и NP.

Равны ли классы сложности P и NP?

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

Класс NP — это задачи, правильность ответа на которые можно быстро проверить. Например, задача о сумме. Предположим, что у вас есть монеты номиналом 2, 3, 5, 6 и 7 рублей, по одной каждого номинала, и вы хотите без сдачи оплатить покупку стоимостью 21 рубль. Можно ли набрать из данных монет сумму, равную 21?

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

Суть «задачи тысячелетия» формулируется так: равны ли классы P и NP? Если легко проверить правильность решения задачи, может ли быть так же легко решить эту задачу? Большинство специалистов уверены, что ответ отрицательный. Однако доказать этого пока никто не смог. Если же вдруг окажется, что P = NP, то человечество ждет переворот в криптографии.

Это был отрывок из статьи для понимания задачи. Я хочу уточнить: если я найду алгоритм, при помощи которого смогу найти все варианты получения суммы 21, то это значит, что я решил задачу? Можно ли использовать алгоритм, написанный на каком-нибудь языке программирования, ну например на языке Pascal, или я должен использовать для решения этой задачи только формулы и т.д. из математики?

0

Сообщение от aleksey_konstr значит, что я решил задачу?

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

Сообщение от aleksey_konstr ну например на языке Pascal

Можно на любом языке, поскольку существует понятие временной сложности алгоритма - в примере с монетками сложность
нахождения суммы будет O(n) -- а вот поиск набора в худшем случае O(n!)

1

Ваше заблуждение заключается в том, что нужно работать не с конкретными числами 2, 3, 5, 6, 7 и 21, а с числами m1, m2, ..., mk и N, т.е. решить задачу в общем виде.
Для частных случаев возможны простые решения, например, взять 30 монет с номиналом 1 рубль и из них сложить 21 рубль. Вот вам и P-алгоритм)))

0

Сообщение от Mikhaylo простые решения

Тут есть, что порешать:

https://en.wikipedia.org/wiki/... e_problems

0

Да, теперь я понял - если моя программа найдёт набор монет, которые в сумме будут давать нужное число и это будет сделано быстрее, чем человек успеет посчитать сумму этих монет, значит я смог решить эту задачу. Большое спасибо.

0

Не решайте задачу тысячелетия, пожалуйста!)))

0

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

не надо ничего перебирать.

21 - (2 + 3 + 5+ 6 + 7) = - 2 надо исключить двойку, чтобы набрать без сдачи
21 - (1 + 3 + 5 + 6) = -1 исключить единицу.
21 − (1 + 4 + 5 + 6 + 7) = -2 Такого числа в списке слагаемых нет, что что исключать нечего и решения не имеет.
7 - (1+2+4+5) = -5
7 - (2+2+4+5) = -6 - решения не имеет.

0

Сообщение от sodda не надо ничего перебирать.

Наберите 21 рупь следующими номиналами: { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }

0

Сообщение от vantfiles Наберите 21 рупь следующими номиналами: { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 }

работает до десятки среди слогаемых. поле десятки показывает сколько из суммы нужно вычесть, чтобы насчитать без сдачи.
если измять 10 и 11 из этого списка, то выйдет 115.
Но это зависит от числа - четное или нечетное и есть ли единицы среди слагаемых.
нужно искать и вычленять закономерности

0

Сообщение от sodda нужно искать

а это и есть - перебор

0

Сообщение от vantfiles а это и есть - перебор

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

0

Сообщение от sodda вычленение закономерностей

В случайно сгенерированном множестве? Увольте.

0

Сообщение от vantfiles а это и есть - перебор

например 25 - (1+2+5+9+17+3) = -12. берем из этого ряда слагаемых 9+3 и убираем. и получаем 25.
но если мы сделаем 25 - (2+2+5+19) = -3 Очевидно, что мы тройку никак убрать не можем.
однако если 24 - (2+2+5+19) = -4 то уже можем. видим зависимость от четности числа и возвращаемого значения.

Добавлено через 53 секунды

Сообщение от vantfiles В случайно сгенерированном множестве? Увольте.

до конкретного предела пожалуй. хотя бы до ста.
а дальше уже дальше думать)

0

Сообщение от sodda например 25 - (1+2+5+9+17+3) = -12. берем из этого ряда слагаемых 9+3 и убираем. и получаем 25.

А вы это алгоритмически то опишите, как и откуда взялись эти числа 9+3...

0

Сообщение от vantfiles А вы это алгоритмически то опишите, как и откуда взялись эти числа 9+3...

если среди слагаемых есть такие, которые в сумме дают 12.

0

Сообщение от sodda не надо ничего перебирать. 21 - (2 + 3 + 5+ 6 + 7) = - 2 надо исключить двойку, чтобы набрать без сдачи

Есть две задачи одинаковой сложности:

Можно ли набрать из монет {2, 3, 5, 6, 7} сумму, равную 21?
Можно ли набрать из монет {2, 3, 5, 6, 7} сумму, равную (2 + 3 + 5 + 6 + 7 - 21)?

Обе решаются перебором, но для одной из них перебор может быть существенно меньше из-за быстрого отсечения. Можно ли набрать 2 из {2, 3, 5, 6, 7}? Как только сумма больше 2, вариант отсекается. То есть, отсекается почти всё. Повезло в данном конкретном случае.

0

Сообщение от Shamil1 Можно ли набрать из монет {2, 3, 5, 6, 7} сумму, равную (2 + 3 + 5 + 6 + 7 - 21)?

у нас есть монеты номиналом -21?

Добавлено через 3 минуты

Сообщение от Shamil1 Можно ли набрать из монет {2, 3, 5, 6, 7} сумму, равную (2 + 3 + 5 + 6 + 7 - 21)?

Говорю, что можно, если убрать цифры 21 и 2.
21 + (2 + 3 + 5 + 6 + 7 − 21) = 23

0

Сообщение от sodda если среди слагаемых есть такие, которые в сумме дают 12.

Вы это перебором нашли.

Когда сумма, которую надо набрать близка к 0 или к сумме всех имеющихся монет, то количество вариантов, которые нужно перебрать и проверить, сильно уменьшается.
Когда мы говорим о "задаче тысячелетия", нас интересует решение в общем виде - для любых входных данных.

0

Сообщение от sodda у нас есть монеты номиналом -21?

Ну не совсем монета, а ценная бумага, называется вексель.

0

Сообщение от vantfiles Ну не совсем монета, а ценная бумага, называется вексель.

Задача была про монеты. А вексель - это воздух. Долговое обязательство.

Добавлено через 1 минуту

Сообщение от Shamil1 Вы это перебором нашли.

нет. это нашел одним действием.
оно не всегда работает в одном ключе, если среди слагаемых есть цифры больше десятки, но действие одно.

0