Не детерминированный полином (NP) против полинома (P)?

Question

Я действительно ищу описание, что на самом деле означает NP alogrithm, и какой тип алгоритма/проблемы можно классифицировать как проблема NP

Я прочитал много ресурсов в сети. Мне понравилось

1. https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard
2. What are the differences between NP, NP-Complete and NP-Hard?
3. Non deterministic Turing machine
4. What are NP problems?
5. What are NP and NP-complete problems?

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

Теперь я понимаю Полиномиальную проблему. Но не в состоянии противопоставить его NP.

NP (недетерминировано Полином Задача): -

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

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

Один из примеров, приведенных во второй ссылке, упомянутой выше, - это Integer factorization is in NP. This is the problem that given integers n and m, is there an integer f with 1 < f < m, such that f divides n (f is a small factor of n)?, почему это не может быть разрешено в течение какого-то полиномиального времени на обычном компьютере? мы можем проверить все числа от 1 до n, если они делят n или нет. Правильно ? Также здесь появляется часть проверки (я имею в виду, если она может быть решена в полиномиальное время, а затем, как решение проблемы может быть проверено в полиномиальное время)?

Answer 1

Ваш вопрос затрагивает несколько пунктов.

Во-первых, в смысле, относящемся к вашему вопросу, размер проблемы определяется как размер Представление проблемы. Так, например, когда вы пишете о проблеме делителя n. Что представляет собой n? Это серия символов длиной q (я не хочу быть более конкретным, чем это). В общем случае n является экспоненциальным в q. Поэтому, когда вы говорите про простой цикл от 1 до n, вы говорите о чем-то экспоненциальном по размеру ввода. Например, число «999999999999999» представляет номер 999999999999999. Это довольно большое количество, но здесь представлено 12 символов.

Во-вторых, в то время как существует более чем один способ определения класса NP, возможно, самый простой для решения решения (что является типом, который вы поднимаете в своем вопросе, а именно что-то истинное или нет) заключается в том, что если ответ верен, тогда есть «сертификат», который может быть проверен в полиномиальное время. Например, рассмотрим Hamilton Path Problem. Это (возможно) трудная проблема для решения, но, если вам дали путь хамильтона в качестве ответа, очень легко проверить, что это так; в частности, это можно сделать в полиномиальное время. Для проблемы пути Гамильтона путь является полиномиально-проверяемым временем сертификатом, и поэтому эта проблема является NP.

Answer 2

Полиномиальное время: - Проблема, которая может быть решена за полиномиальное время ввода, называется полиномиальной проблемой. Простыми словами: - Здесь Решение проблемы выполняется быстро. Для примера сортировки, бинарный поиск

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

Но неформально люди во время разговора/сообщений используют термин NP в смысле ниже Проблема, которая не может быть решена за полиномиальное время ввода, называется полиномиальной проблемой. Простыми словами: - Здесь Решение проблемы не быстрое. Возможно, вам придется попробовать другую перестановку/комбинацию или угадывание. Но часть проверки выполняется быстро и может быть выполнена в полиномиальное время. Например, введите некоторые числа X и разделите числа на две группы, что различие в их сумме минимально

Мне очень понравился ответ Алекс Флинт на https://www.quora.com/What-are-P-NP-NP-complete-and-NP-hard. Суть в том, что это просто суть.