Матаны, объясните мне проблему P vs. NP на пальцах.
Пожалуйста.

GD Star Rating
loading...

20 Responses to Матаны, объясните мне проблему P vs.

  1. Peein:

    Одним предложением проблема P vs NP такова: правда ли, что если у какой-то задачи легко проверить корректность ответа (зная ответ), то и найти этот ответ (не зная изначально) тоже легко.

    Существует большой класс задач, у которых, зная ответ, легко убедиться, что он верен. Например, несложно удостовериться, что текст расшифрован правильно, если известен секретный ключ. Или, скажем, несложно проверить, является ли данное число составным, если даны его множители. Или, скажем, легко убедиться, что лабиринт можно пройти, если дан возможный путь прохождения этого лабиринта. Множество таких задач называется NP (nondeterministic polynomial).

    Очевидно, часть этих задач такова, что не только проверить решение, но и найти это решение «с нуля» тоже можно эффективным алгоритмом. Например, для большинства лабиринтов найти путь в них не очень сложно. Проверка числа на простоту тоже, оказывается, делается условно-эффективно без знания множителей. Множество таких задач называется P. Очевидно, каждая задача типа P является также задачей типа NP.

    Интуитивно кажется, однако, что не каждая задача типа NP является типом P, т.е. наверняка не все задачи, у которых легко проверить ответ, должны легко решаться с нуля. Должны по идее существовать «хорошие загадки». Такие, где фиг найдешь ответ, но как только найдешь — то сразу легко всё проверить.

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

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

  2. Noeich:

    Благодарю покорно. Думаю выскажу общее мнение, что объясненние дано в лучших традициях зарекомандовавшего себя здесь метода. Sleep — молодец!

    А почему бы не продолжить тему и не объяснить на пальцах, как общее доказательство данной проблемы (которое, судя по всему, будет лежать в областях крайне далеких математических абстракций) поможет поиску частных решений практических задач той же криптографии или решению задачи коммивояжера.

  3. Zvnre:

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

    Если будет доказано, что P!=NP, значит будет окончательно установлено, насколько хороши могут быть алгоритмы для тех или иных задач и после какого-то предела поиски и разработку новых алгоритмов можно будет прекратить, а заодно относительно расслабиться насчет шифрования.

    И, на всякий случай, задача взлома алгоритма шифрования RSA не имеет прямого отношения к этой проблеме, так что как бы оно ни вышло с P vs. NP, алгоритмы разложения чисел на простые множители можно будет продолжать искать.

  4. Ef7one:

    Из всех примеров NP-задач мне более всего нравится задача о булевой выполнимости формул. Берёшь n бинарных переменных, затем комбинируешь из них операцией ИЛИ кляузы, скажем по 3 переменных в кляузе, а все кляузы объединяешь операцией И. В итоге, если загадана некоторая комбинация переменных (слово), записать под неё выполнимую булеву формулу не составляет труда, а вот имея эту булеву формулу догадаться о загаданном слове можно только за время, пропорциональное 2n (вкратце — тупой перебор). Это будет 3-SAT проблема, которая имеет важные практические применения, например, в автоматизации проектирования топологии СБИС. Вроде как она ограничивает сегодня дальнейший рост сложности цифровой электроники. Есть журналы только по SAT-проблеме, делаются всякие открытые ресурсы и конкурсы по решателям, в спонсорах можно увидеть производителей цифровой электроники. Задача по формулировке офигенно проста, объяснить её можно хоть 10-летнему ребёнку. Для 2-SAT доказано существование полиномиальных алгоритмов, т.е. время решения не степенная функция от размера слова n, а полином какой-то там степени. Что делает её решение реальным для гораздо больших n. А для 3-SAT доказана NP-полнота (кто совсем в теме — объясните плз!). Это вроде как сводимость любой NP задачи к задаче 3-SAT за полиномиальное время. В том числе и задачи о разложении на множители, кстати, я так думал. И если P=NP найдётся тут, то вроде как не только капец методам шифрования с открытым ключом, но и ура-прорыв в процессоростроении. Явно немало людей занимаются этой задачкой, а публикаций сравнительно мало, особенно если учитывать прямую связь задачки с P=NP?, которая wanted 1m$ от института Клэя. Встречал смешные на первый взгляд публикации, вроде «Доказана недоказуемость проблемы..», остаётся дождаться «Доказана недоказуемость недоказуемости..».

  5. CopRU:

    Самое главное — есть класс NP-полных задач (NP-complete), к которым полиномиально сводятся все NP, навскидку — задача коммивояжера или раскраски графа или нахождения гамильтоновых циклов в графе. Все эти задачи сводятся друг к другу полиномиально.
    Так вот, если будет найдено полиномиальное решение для какой-нибудь из этих задач, это автоматически означает, что P=NP.

  6. Peein:

    Строго говоря, всё зависит от доказательства. Если (что очень маловероятно), кто-то обнаружит доказательство P=NP, скорее всего это будет очень неконструктивное доказательство. Т.е. мы узнаем, что для задач, у которых мы раньше знали лишь как проверять ответ, можно оказывается и находить ответ за полиномиальное время, но при этом ни одного конкретного алгоритма от этого не появится. И раз мы такой алгоритм до сих пор не нашли, знание что «он где-то есть» обнадеживает, но не помогает.

    задача взлома алгоритма шифрования RSA не имеет прямого отношения к этой проблеме,

    Как я уже заметил, любое шифрование с открытым ключом имеет прямое отношение. Формально, пусть тебе дана шифровка публичным ключом какого-то сообщения. Вопрос — какой у данного сообщения первый бит? Это типичная NP-задача: зная секретный ключ проверить, что бит равен единице, легко. При этом она (скорее всего) не P задача — не зная секретного ключа вычислить бит можно, но очень сложно. Если вдруг окажется, что бит можно вычислять без секретного ключа не менее эффективно, чем с ним (а так будет если P=NP), то шифрование будет сломано.

    Аналогично с разложением на множители. Чтобы понять сформулируй задачу в виде «узнать к-тый бит самого маленького множителя данного числа». Это типичное NP. Если известно разложение на множители — бит проверяется тривиальным образом. Если нет — всё гораздо сложнее.

  7. Peein:

    А для 3–SAT доказана NP–полнота (кто совсем в теме — объясните плз!)

    Объясняю. Задача называется NP-полной, если к ней можно (полиномиально) свести любую другую NP задачу. Другими словами, умея решать эффективно NP-полную задачу, мы сможем эффективно решить любую другую NP-задачу.

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

    Например, условие «число А раскладывается на множители B, C, D» можно записать довольно длинной, но всё же булевой формулой, в которую пойдут в качестве переменных биты чисел A, B, C, D, а значение формулы будет «True», если разложение корректно.

    Поэтому если мы не знаем как эффективно решать задачу разложения на множители, но умеем эффективно находить решения булевых формул, мы в шоколаде — переформулируем нашу задачу разложения в виде соответствующей формулы, применяем известный нам метод решения булевых формул, и ура — вычитываем из решения формулы биты разложения числа на множители. Аналогичная логика применима к любой другой NP задаче: чтобы свести ей к SAT нам надо лишь записать алгоритм проверки решения в виде булевой формулы.

    Поэтому SAT является NP-полной.

  8. Zvnre:

    про RSA это я к тому, что хотя задача и сводима к NP, но даже если P!=NP, это не значит, что для взлома RSA нет полиномиального алгоритма.

  9. Ef7one:

    А вот ниже написал, что найдя полиномиальный алгоритм для любой из NP-полных задач мы автоматически доказываем P=NP. Это взаправду так? Совершенно любой задачи, граф раскрасим, например или ту же 3-SAT решим. Сводятся ли NP-полные задачи друг к другу? Думаю, что да, хочется обрести уверенность окончательно. Очень привлекательно, учитывая прочитанный где-то случай про внезапное и офигенно простое решение одной из проблем Гильберта (это аналог семи проблем тысячелетия, только для ХХ века) 10-классником.

  10. Zvnre:

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

  11. Peein:

    Да, конечно. В этом и определение NP-полной задачи — к ней можно свести любую другую NP задачу (в том числе другую NP-полную).

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

  12. Peein:

    Ну это ты в другую сторону импликацию имеешь в виду.

    На эту тему конечно стоит заметить, что даже если задача объявлена NP-полной, это не значит что ее всегда трудно решить. Например, решение булевой формулы «в общем виде» сложно. Однако ж для многих конкретно взятых булевых формул можно подогнать ответ хитрым угадыванием.

    Поэтому криптография конечно же опирается на гораздо более солидные предположения, нежели P!=NP. Недостаточно постулировать, что «существуют типы задач для которых иногда трудно найти ответ». В криптографии нужно предполагать, что «существуют типы задач, для которых ПОЧТИ ВСЕГДА трудно найти ответ». И вот на них строятся шифры, подписи, и прочее.
    Однако ж все эти предположения (солидные ли, или нет) развалятся, если окажется что P=NP.

  13. M2yod:

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

    Только задачи не из серии «проектирования топологий СБИС за полиномиальное время», а из серии «у Васи 4 яблока, а у Пети 6». Понимаю, что чем проще примеры, тем дальше они от реальности (поверьте, я понимаю это лучше всех! 🙂

    Но я и не собираюсь лично решать проблему P vs. NP. Лишь хочу получше понять, про что она.

  14. Ef7one:

    Разводка печатных плат сводится к 3-SAT в общем случае. Очень похожа на «топологий СБИС» и, на самом деле, близка к серии про Васю и Петю. С человеческого языка «можно провести дорожку Х в слое 1 или 2 или 3 или 4» переводится на язык логического ИЛИ для одной дорожки, затем для всех дорожек X собирается большое И. Упрощённо так, ещё условия зазоров, непересечения и куча других мелочей. Что слоёв не три, а больше — не беда, можно подсмотреть как n-SAT запросто сводится к 3-SAT в википедиях. Это же клёво, когда знаешь, что если решение не найдено, то его не существует, а если найдено, то выбираешь из лучшего. Сейчас можно только сомневаться в некоторых случаях. Хотя бы это вот сулит P=NP.
    Аналогично, буду рад услышать ещё примеры.

  15. Peein:

    Живые примеры задач типа NP везде вокруг тебя:
    — Паззлы, судоку, кроссворды, шахматные задачи и прочие газетные головоломки (где имея решение легко понять, что оно верно). Самый явный пример — задача типа «найди на картинке два отличия».
    — Сортировка вещей по порядку (посмотрев на отсортированные вещи легко убедиться, что они отсортированы) или любая другая обработка данных с четким критерием корректности.
    — Уже упомянутая выше электронная подпись (корректность ее легко проверяется)
    — Ты просил про Васю и яблоки. Вот тебе тупейшая задача из класса NP: сделать так чтобы у Васи в каждой руке было по N яблок. Нуаче — если я сделаю, чтобы было по N ты ведь сможешь проверить, что я всё правильно сделал?

    Другими словами, NP — это всё то, что «можно проверить», начиная от самого тупого. Поэтому в целом NP — это очень хороший класс задач (вне зависимости от того, «легкие» они (P) или «трудные» (NP-complete)). Чтобы понять, почему он хороший — вот тебе примеры задач «не из NP» (в кавычках, потому что если очень строго подходить к делу, неполиномиальность этих примеров можно местами оспорить, но это сейчас не важно):
    — Найти самый длинный палиндром. Даже если я покажу тебе очень длинный палиндром и скажу, что «я решил», ты не сможешь убедиться в том, что это верное решение, не пересмотрев-таки весь словарь.
    — Аналогично, задачи типа «найти самый быстрый путь» куда-то там, «самое красивое решение» чего-то там, итд обычно не относятся к NP, т.к. фиг проверишь, что нельзя лучше.
    — Задачи распознавания изображений, перевода текста, итд, зачастую не относятся к NP т.к. нет четких и легко проверяемых критериев, правильно ли ты распознал изображение или нет. Приходится надеяться на везение.

    Раз решение задачи типа NP можно проверить, значит для любой NP задачи мы можем написать алгоритм решения. Он будет следующий — перебираем все возможные решения и для каждого проверяем, правильно ли оно. Это конечно ужасно неэффективно, но тем не менее это алгоритм, который найдет решение. У задач не из NP может и такого не оказаться.

    Очевидно, однако, что последовательное пробование всех ответов — это как-то тупо, и многие задачи можно решить как-то «схитрив», «напрямую». Вот, к примеру, задача сортировки. Конечно можно начать перебирать все последовательности до тех пор пока не встретится та, которая отсортирована, но немного подумав можно придумать хитрый способ отсортировать последовательность и побыстрее. Поиск пути в лабиринте можно сделать пошагово, без нужны перебирать все возможные пути. Или в примере про Васю — я конечно могу совать ему в руки поочередно разное количество яблок до тех пор пока не случится так, что в обоих по N, но можно не тупить, и сразу положить в обе руки по N яблок, т.к. мы знаем как это делается. Вот все задачи, где можно найти «хитрость» и решить их, не проверяя все варианты втупую по сути являются классом P.

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

  16. M2yod:

    О, уже лучше! Задача «про яблоки» не обязательно должна быть прям про яблоки. Но она должна быть описана простыми словами (без полинормальных многочленов), там у Васи было три любовницы, а у Пети одна, но Анджелина Джоли и т.д.

  17. CopRU:

    Последнее утверждение не совсем верно. С очень многими задачами, как выше писалось, эти хитрости есть. Тот же RSA считается уязвимым, когда простые ключи отличаются более чем в ~2-4 раза, даже когда они длинные. И полиномиальность алгоритма совсем не гарантирует, что найдется эффективный алгоритм расчета. Вот сейчас вылетело из головы, но есть какая-то задача… в общем, в теории чисел, несколько лет назад какой-то перец ее решил. Что-то с перемножением матриц, в общем, нашелся полиномиальный алгоритм, но степень полинома такая, что только плакать и размазывать слезы по лицу.

  18. CopRU:

    Да, взлом RSA — это вообще плохой пример. Про него неизвестно не то что даже является ли она NP-полной (и, насколько мне известно, многие склоняются к тому, что нет), но даже и то, эквивалентен ли он по сложности факторизации.

  19. CopRU:

    Ну, определения не дают тебе никакой информации.
    Информация взялась из того, что про конкретные задачи было ДОКАЗАНО, что они NP-полные.

  20. Peein:

    С очень многими задачами, как выше писалось, эти хитрости есть

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

    полиномиальность алгоритма совсем не гарантирует, что найдется эффективный алгоритм расчета.

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

Добавить комментарий