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


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

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

6 203

6 ответов:

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

определение:

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

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

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

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

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

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

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

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

  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 миллион долларов.

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

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

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

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

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

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

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

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

краткое резюме из моего скромного знания:

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

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

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

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

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

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

во-первых, некоторые определения:

  • конкретная проблема находится в 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 - это " проблемы, разрешимые a Nондетерминированная машина Тьюринга в Pвремя olynomial". Хотя это говорит вам, откуда взялось имя, это не дает вам такого же интуитивного ощущения того, что такое проблемы NP.

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

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

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

обратите внимание, что экземпляр 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'ing вместе все эти ограничения дает булеву формулу, которая имеет размер полинома (O(n+m)). Вы можете проверить, что требуется полиномиальное время для вычисления как ну: вы делаете прямо O(1) материал на вершину и на ребро.

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

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

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