Что такое "P=NP?", И почему это такой знаменитый вопрос?

Question

Вопрос о том, является ли P=NP, возможно, самым известным во всей информатике. Что это значит? И почему это так интересно?

Да, и для дополнительной информации, пожалуйста, опубликуйте доказательство истинности или ложности заявления.:)

Answer 1

P обозначает полиномиальное время. NP обозначает недетерминированное полиномиальное время.

Определения:

• Полиномиальное время означает, что сложность алгоритма составляет O(n^k), где n - это размер ваших данных (например, количество элементов в списке, которые нужно отсортировать), а k - это константа.

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

• Операция - это то, что имеет смысл в качестве основной операции для конкретной задачи. Для сортировки основная операция представляет собой сравнение. Для умножения матрицы основной операцией является умножение двух чисел.

Теперь вопрос в том, что означает детерминированный против недетерминированного. Существует абстрактная вычислительная модель, воображаемый компьютер, называемый машиной Тьюринга (ТМ). Эта машина имеет конечное число состояний и бесконечную ленту с дискретными ячейками, в которые можно записывать и считывать конечный набор символов. В любой момент времени ТМ находится в одном из своих состояний и смотрит на конкретную ячейку на ленте. В зависимости от того, что он читает из этой ячейки, он может записать новый символ в эту ячейку, переместить ленту на одну ячейку вперед или назад и перейти в другое состояние. Это называется переходом между состояниями. Удивительно, но, тщательно создавая состояния и переходы, вы можете создать TM, который эквивалентен любой компьютерной программе, которая может быть написана. Вот почему он используется в качестве теоретической модели для доказательства того, что компьютеры могут и не могут делать.

Здесь нас интересуют два вида ТМ: детерминированные и недетерминированные. Детерминированный TM имеет только один переход из каждого состояния для каждого символа, который он считывает с ленты. Недетерминированный TM может иметь несколько таких переходов, то есть он может проверять несколько возможностей одновременно. Это похоже на создание нескольких потоков. Разница в том, что недетерминированный TM может порождать столько "потоков", сколько ему нужно, в то время как на реальном компьютере одновременно может выполняться только определенное количество потоков (равное количеству процессоров). На самом деле компьютеры - это в основном детерминированные ТМ с конечными лентами. С другой стороны, недетерминированная ТМ не может быть физически реализована, разве что с помощью квантового компьютера.

Было доказано, что любая проблема, которая может быть решена с помощью недетерминированной ТМ, может быть решена с помощью детерминированной ТМ. Однако неясно, сколько времени это займет. Утверждение P=NP означает, что если задача занимает полиномиальное время на недетерминированной ТМ, то можно построить детерминированную ТМ, которая бы решала ту же проблему и за полиномиальное время. Пока что никто не смог доказать, что это возможно, но никто так и не смог доказать, что это невозможно.

NP-полная задача означает NP-задачу X, такую ​​что любая NP-задача Y может быть сведена к X полиномиальной редукцией. Это означает, что если кто-нибудь когда-нибудь придет к решению задачи с NP-полиномами за полиномиальное время, это также даст решение за NP-задачи за полиномиальное время. Таким образом, это докажет, что P=NP. И наоборот, если кто-то докажет, что P!=NP, то мы были бы уверены, что на обычном компьютере невозможно решить проблему NP за полиномиальное время.

Примером NP-полной проблемы является проблема поиска истинного присваивания, которое сделало бы булево выражение, содержащее n переменных истинным.
На данный момент на практике любую задачу, которая занимает полиномиальное время для недетерминированной ТМ, можно решить только за экспоненциальное время на детерминированной ТМ или на обычном компьютере.
Например, единственный способ решить проблему назначения правды - это попробовать 2^n возможностей.

Answer 2

1. Проблема да-или-нет в P (P полиномиальное время), если ответ может быть вычислен за полиномиальное время.
2. Проблема да-или-нет в NP (N на детерминированном P полиномиальном времени), если ответ "да" можно проверить за полиномиальное время.

Интуитивно понятно, что если проблема в P, то в NP. Учитывая потенциальный ответ на проблему в P, мы можем проверить ответ, просто пересчитав ответ.

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

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

Большинство ученых считают, что P! =NP. Однако доказательств для P = NP или P! =NP пока не установлено. Если кто-либо предоставит доказательства для какой-либо гипотезы, он выиграет 1 миллион долларов США.

Answer 3

Чтобы дать самый простой ответ, я могу думать о:

Предположим, у нас есть проблема, которая принимает определенное количество входных данных и имеет различные потенциальные решения, которые могут или не могут решить проблему для заданных входных данных. Хорошим примером может служить логическая головоломка в журнале головоломок: входные данные - это условия ("Джордж не живет в синем или зеленом доме"), а потенциальным решением является список утверждений ("Джордж живет в желтом" дом, выращивает горох и владеет собакой "). Известным примером является проблема коммивояжера: с учетом списка городов, времени, в которое можно добраться из любого города в любой другой, и ограничения по времени, потенциальным решением будет список городов в том порядке, в котором их посетит продавец, и это сработало бы, если бы сумма времени в пути была меньше, чем срок.

Такая проблема в NP, если мы можем эффективно проверить потенциальное решение, чтобы увидеть, работает ли оно. Например, учитывая список городов для посещения продавцом по порядку, мы можем сложить время для каждой поездки между городами и легко увидеть, не превышает ли это ограничение по времени. Проблема в P, если мы можем эффективно найти решение, если оно существует.

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

Следовательно, проблема P=NP может быть выражена следующим образом: если вы можете эффективно проверить решение для задачи описанного выше типа, можете ли вы найти решение (или доказать, что оно не существует) эффективно? Очевидный ответ: "Почему ты должен это делать?", И именно здесь дело обстоит сегодня. Никто не смог доказать это, так или иначе, и это беспокоит многих математиков и компьютерщиков. Вот почему любой, кто может доказать это решение, может получить миллион долларов от Фонда Клэйпул.

Мы обычно предполагаем, что P не равен NP, что нет общего способа найти решение. Если бы оказалось, что P=NP, многое изменилось бы. Например, криптография стала бы невозможной, а вместе с ней - какая-либо конфиденциальность или возможность проверки в Интернете. В конце концов, мы можем эффективно взять зашифрованный текст и ключ и создать оригинальный текст, поэтому, если P=NP, мы могли бы эффективно найти ключ, не зная его заранее. Взлом пароля станет тривиальным. С другой стороны, есть целые классы проблем планирования и распределения ресурсов, которые мы могли бы эффективно решить.

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

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

Answer 4

Краткое изложение моих скромных знаний:

Есть несколько простых вычислительных задач (например, нахождение кратчайшего пути между двумя точками на графике), которые можно вычислить довольно быстро ( O(n^k), где n - размер входных данных, а k - постоянная (в случай графиков, это количество вершин или ребер)).

Другие проблемы, такие как поиск пути, который пересекает каждую вершину графа или получение закрытого ключа RSA из открытого ключа, сложнее (O(e^n)).

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

Это интересно, потому что никто даже не имеет представления о решении. Некоторые говорят, что это правда, некоторые говорят, что это неправда, но нет единого мнения. Еще одна интересная вещь заключается в том, что решение будет вредным для шифрования с открытым / закрытым ключом (например, RSA). Вы можете сломать их так же легко, как генерирование ключа RSA сейчас.

И это довольно вдохновляющая проблема.

Answer 5

Я мало что могу добавить к вопросу о том, что и почему в P=?NP, но в отношении доказательства. Мало того, что доказательство стоило бы некоторого дополнительного кредита, но оно решило бы одну из проблем тысячелетия. Недавно был проведен интересный опрос, и опубликованные результаты (PDF) определенно стоит прочитать в отношении предмета доказательства.

Answer 6

Сначала несколько определений:

• Особая проблема в P, если вы можете вычислить решение за время меньше n^k для некоторых k, где n это размер ввода. Например, сортировка может быть сделана в n log n который меньше чем n^2 Таким образом, сортировка полиномиального времени.

• Проблема в NP, если существует k такое, что существует решение размера не более n^k который вы можете проверить вовремя самое большее n^k, Возьмем 3-цветную окраску графиков: для данного графика 3-цветная окраска - это список пар (вершина, цвет), размер которых O(n) и вы можете проверить вовремя O(m) (или же O(n^2)) все ли соседи имеют разные цвета. Таким образом, граф является 3-раскрашиваемым, только если существует короткое и легко проверяемое решение.

Эквивалентное определение NP- "задачи, решаемые N- недетерминированной машиной Тьюринга за полиномиальное время". Хотя это говорит вам о том, откуда взято имя, оно не дает вам того же интуитивного ощущения того, на что похожи проблемы NP.

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

Почему вопрос P =? NP интересно? Чтобы ответить на этот вопрос, нужно сначала увидеть, что такое NP-полная проблема. Проще говоря,

• Задача L является NP-полной, если (1) L находится в P и (2) алгоритм, который решает L, может быть использован для решения любой проблемы L'в NP; то есть, учитывая экземпляр L', вы можете создать экземпляр L, который имеет решение, если и только если экземпляр L' имеет решение. Формально говоря, каждая проблема L'в NP сводима к L.

Обратите внимание, что экземпляр L должен быть вычисляемым за полиномиальное время и иметь полиномиальный размер, равный размеру L'; таким образом, решение NP-полной задачи за полиномиальное время дает нам решение всех NP задач за полиномиальное время.

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

Для каждой вершины v есть две логические переменные v_h и v_l и требование (v_h или v_l): каждая пара может иметь только значения {01, 10, 11}, которые мы можем рассматривать как цвета 1, 2 и 3.

Для каждого ребра (u, v) необходимо, чтобы (u_h, u_l)!= (V_h, v_l). То есть,

not ((u_h and not u_l) and (v_h and not v_l) or ...) перечисление всех равных конфигураций и условие, что ни одна из них не соответствует действительности.

AND Объединение всех этих ограничений дает булеву формулу, которая имеет полиномиальный размер (O(n+m)). Вы можете проверить, что для вычисления также требуется полиномиальное время: вы делаете прямо O(1) материал на вершину и на ребро.

Если вы можете решить булеву формулу, которую я создал, то вы также можете решить раскраску графа: для каждой пары переменных v_h и v_l пусть цвет v будет соответствовать значению этих переменных. По построению формулы у соседей не будет одинаковых цветов.

Следовательно, если 3-раскраска графов является NP-полной, то и выполнимость булевой формулы.

Мы знаем, что 3-раскраска графов является NP-полной; однако, исторически мы узнали, что, сначала показывая NP-полноту булевой контурируемости, а затем уменьшая ее до 3-цветности (а не наоборот).