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

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

Интуитивно мы можем видеть, что если проблема заключается в P, тогда это находится в НП.Дан потенциальный ответ на проблему в P, мы можем проверить ответ, просто пересчитав ответ.

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

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

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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

Но CS speak сообщает, что проблема в том, что мы не можем "преобразовать" недетерминированную машину Тьюринга в детерминированную, однако мы можем преобразовать недетерминированные конечные автоматы (такие как анализатор регулярных выражений) в детерминированные (ну, вы можете, но время выполнения машины займет много времени).То есть мы должны испробовать все возможные пути (обычно умные профессора 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ондетерминистическая машина Тьюринга в Pолиномиальное время".Хотя это говорит вам, откуда взялось название, это не дает вам такого же интуитивного представления о том, что такое 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-полная, то и выполнимость булевой формулы также является NP-полной.

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