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

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

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

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

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

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

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

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

0

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

Нет. Для наглядности я не стал производить арифметические действия.

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

Фактически, это одна и та же задача. И, очевидно, что проверить все варианты "как набрать сумму 2" довольно легко. Повезло, что требуется набрать такую маленькую сумму, которая меньше почти всех имеющихся монет.

0

Сообщение от sodda Задача была про монеты.

Чёрт, я сразу то и не понял...

Lisp 198 17
Священные войны 168 1
Непризнанные теории, гипотезы 167 3

0

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

Это понятно. Но чтобы говорить об общим случае, надо рассмотреть и изучить частные.

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

Сообщение от vantfiles Lisp 198 17 Священные войны 168 1 Непризнанные теории, гипотезы 167 3

Я не знаю откуда это, но автор написал в посте про монеты.

0

Сообщение от sodda нет. это нашел одним действием.

Невозможно это одним действием действием.

(1+2+5+9+17+3)
Вы сначала перебрали все 6 чисел и убедились, что среди них нет 12.
Затем Вы начали перебирать все 15 пар чисел, складывать и сравнивать сумму с 12. Такая пара нашлась. Поэтому Вы не стали проверять все тройки чисел.

0

0

Сообщение от Shamil1 Невозможно это одним действием действием.

вот же оно
21 - (1+2+5+9+17+3) = -16
Да, я глазами вижу, что если из этого ряда вычесть сумму чисел, которая равна 16 - 9+5+1 - то наберем 21 рупь без сдачи.
Я же говорю о необходимости найти способ понять, когда рзультат указывает на невозможность решения, а когда вот на такой вариант.

0

Сообщение от sodda я глазами вижу

Вы перебираете числа глазами. Тем не менее, перебор остаётся перебором. В данном случае числа расположены компактно, и Вы можете посмотреть сразу на все. К тому же, их мало, поэтому Вы можете все их запомнить. Если бы числа были расположены в книжке по одному на странице, то Вам бы пришлось перебрать (пролистать) все страницы. А если бы их было столько, сколько Вы не можете запомнить, то Вам бы пришлось перебирать несколько раз. Точное количество раз зависит от того, насколько быстро Вам повезёт подобрать нужную сумму (в данном случае - 16 или 21).

0

Сообщение от Shamil1 Вы перебираете числа глазами. Тем не менее, перебор остаётся перебором. В данном случае числа расположены компактно, и Вы можете посмотреть сразу на все. К тому же, их мало, поэтому Вы можете все их запомнить. Если бы числа были расположены в книжке по одному на странице, то Вам бы пришлось перебрать (пролистать) все страницы. А если бы их было столько, сколько Вы не можете запомнить, то Вам бы пришлось перебирать несколько раз. Точное количество раз зависит от того, насколько быстро Вам повезёт подобрать нужную сумму (в данном случае - 16 или 21).

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

0

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

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

0

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

Ну вот я вижу одну закономерность. Если среди слагаемых есть единица, то, скорее всего, ответ укажет на ту сумму, которую нужно вычесть из общей суммы, чтобы набрать без сдачи.

0

Сообщение от sodda Ну вот я вижу одну закономерность.

Это бессмысленно, пока не указаны формальные ограничения на входные данные.

Сообщение от sodda Если среди слагаемых есть единица, то, скорее всего, ответ укажет на ту сумму, которую нужно вычесть из общей суммы, чтобы набрать без сдачи.

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

0

Я решил эту задачу тремя способами. Первый способ - самый простой, остальные два - трудные, над ними надо ещё поработать. На решение ушло около пяти часов. Решение занимает около пятнадцати строчек школьной страницы. Сейчас довожу до совершенства алгоритм на языке Паскаль и математические формулы с неизвестными. Задачу можно решить математически или на языке Паскаль. Первый способ - надёжный, но у него есть одно слабое место - это работа с большими числами, на которые возможно уйдёт чуть дольше времени, а может и нет, я не знаю, я тестировал задачу на небольших числах. Сначала я хотел использовать для этого супер быстрый компьютер, но это скорее было бы хитростью, чем выходом из положения. Мне всегда нравятся красивые решения, на которые можно смотреть часами - поэтому я изменил одну формулу и решение стало выполняться быстрее. При решении вторым способом результат получается мгновенно, независимо от величины суммы, но это в теории, надо ещё всё обдумать. У меня есть два вопроса: какая может быть самая большая сумма по условию задачи - миллион, миллиард, триллион и т.д.? Просто я не думаю, что кто-то будет работать с такими огромными числами, но я могу и ошибаться. И второй вопрос или проблема - это работа с большими числами, из-за которых может возникнуть нарушение закономерности внутри этих чисел (я это где-то слышал на лекции по математике) и тогда может возникнуть ошибка, но у меня пока не было никаких ошибок.

0

Учили, но видимо впустую, что ты не знаешь - миллион или миллиард... Тебя учили, но ты не учился.

0

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

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

0

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

Нужно доказывать.

0

Сообщение от Mikhaylo Нужно доказывать.

Знаете случай с замещением бесконечных плоскостей?
Математики раз 5 доказывали, все фигуры которыми можно равномерно замостить бесконечную плоскость известны.
Расчеты там, анализ - все серьезно.
Одна женщина - в прошлом тоже математик - все время опровергала это.
Известная история из области математики.

0

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

0

Добавлено через 2 минуты
Можно ли ваш код увидеть, Алексей? Или вы твердо намерены получить миллион долларов в одни руки?

0

Я не могу показать вам решение этой задачи потому, что мне нужны деньги на мои научные проекты.

0

Сообщение от aleksey_konstr научные проекты

чисто из любопытства, какое у Вас образование, какой ВУЗ закончили?

0