Введение

Когда мы занимаемся комбинаторной оптимизацией, нам нужно решать различные задачи, которые можно разделить на задачи P, NP и NPC в зависимости от сложности задачи. Сегодня я познакомлю вас с такими вопросами.

П проблема

В теории вычислительной сложности P (также известный как PTIME или DTIME) является основным типом сложности. Это относится ко всем проблемам принятия решений, которые могут быть решены за полиномиальное время с использованием детерминированной машины Тьюринга.

Здесь мы даем определение P, если язык формул L является типом P, то тогда и только тогда, когда существует такая детерминированная машина Тьюринга M:

1. Для всех входных данных M выполняется за полиномиальное время.
2. Для всех x в L выход M равен 1
3. Выход M равен 0 для всех x, не входящих в L

Общие проблемы P включают версии линейного программирования для принятия решений, вычисление наибольшего общего множителя и нахождение наибольшего соответствия. В 2002 году было показано, что проблема определения того, является ли число простым, также является P-проблемой.

НП проблема

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

NP фактически состоит из двух этапов: первый этап состоит из угадывания решения, которое генерируется недетерминированным способом, а второй этап состоит из детерминированного алгоритма, который проверяет, могут ли догадки решить проблему. То есть NP = недетерминированный + полиномиальный.

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

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

Примеры проблем NP

В компьютерных науках многие задачи поисковой оптимизации можно рассматривать как задачи NP. Задача коммивояжера — типичная NP-задача.

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

Некоторые проблемы NP трудно решить

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

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

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

проблема с НПС

В теории вычислительной сложности задача, удовлетворяющая следующим условиям, является задачей NPC:

1. Неопределенная машина Тьюринга может быть решена за полиномиальное время.
2. Детерминированные машины Тьюринга могут быть решены с большой временной сложностью (EXPTIME или алгоритм поиска методом грубой силы), а их решения могут быть проверены за полиномиальное время.
3. Его можно использовать для моделирования любой другой задачи с аналогичной разрешимостью (другие задачи в NP могут быть преобразованы или сведены к этой задаче за полиномиальное время).

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

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

Хотя решения проблем с NPC можно проверить «быстро», не существует известного способа быстро найти решение. То есть по мере роста размера задачи время, необходимое для решения задачи с использованием любого известного в настоящее время алгоритма, быстро увеличивается.

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

NP-hard

В теории вычислительной сложности NP-сложно — это описание класса задач, которые «по крайней мере так же сложны, как и самые сложные задачи в NP». Простым примером NP-трудной задачи является задача о сумме подмножеств.

Если известную задачу NPC можно свести к этой задаче, то задача называется NP-сложной.

Таким образом, проблемы с NPC должны быть проблемами NP-Hard, но не все проблемы NP-Hard являются проблемами NPC.

Проблемы P и NP

Проблемы P и NP являются основными нерешенными проблемами информатики. В нем говорится о том, можно ли быстро проверить проблему, можно ли решить ее быстро?

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

В общем, всем задание P! = NP, что означает, что, хотя его нельзя решить за полиномиальное время, ответ можно проверить за полиномиальное время.

В зависимости от того, совпадают ли P и NP, мы делаем диаграмму отношений P, NP, NPC и NP-Hard соответственно.

Эта статья была включена вwoohoo.floydpress.com/04-afraid-even-NPC…

Самая популярная интерпретация, самая глубокая галантерея, самые краткие уроки и множество трюков, о которых вы не знаете, ждут вас!

Добро пожаловать, чтобы обратить внимание на мой официальный аккаунт: «Программируйте эти вещи», разбирайтесь в технологиях, лучше поймите себя!