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

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-красочности (а не наоборот).