Отличие P от NP классов

[esper369]

Mihaylo в сообщении #1063967 писал(а):

Почему существуют задачи класса $P$?

Другими словами - почему для некоторых задач существуют быстрые алгоритмы решения за полиноминальное время?

Для этого рассмотрим задачу поиска в телефонном справочнике телефона по ФИО. Данные в телефонных справочниках отсортированы в алфавитном порядке.
У нас есть 2 алгоритма подходящие для этой задачи:
1) алгоритм полного перебора соответствующий $NP$ классу.
2) и алгоритм бинарного поиска соответствующий $P$ классу.
Бинарный поиск использует внутреннюю упорядоченность (по алфавиту) телефонного справочника и за счет этого он гораздо быстрее перебора.

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

Гипотеза: детерминированность есть необходимое условие для существования быстрых алгоритмов решения задач $P$ класса.
Ну то есть: это необходимое условие существование самого $P$ класса. Именно наличие внутренней структуры, внутренней упорядоченности позволяет нам использовать значительное ускорение по сравнению с алгоритмом перебора.

Именно в этом по моему и есть различие этих классов. Правда из этой гипотезы тут же следует неравенство $P$ и $NP$ классов... Продолжать?

[Aritaborian]

esper369 в сообщении #1429164 писал(а):

Правда из этой гипотезы тут же следует неравенство $P$ и $NP$ классов...

esper369 в сообщении #1429164 писал(а):

Продолжать?

Непременно. Только не здесь; пишите сразу в Институт Клэя.

[Null]

Обе ваших задачи лежат в классе $P$(Вы это доказали), а значит и в $NP$.

[esper369]

Aritaborian в сообщении #1429166 писал(а):

esper369 в сообщении #1429164 писал(а):

Правда из этой гипотезы тут же следует неравенство $P$ и $NP$ классов...

esper369 в сообщении #1429164 писал(а):

Продолжать?

Непременно. Только не здесь; пишите сразу в Институт Клэя.

это тролинг?

Null в сообщении #1429168 писал(а):

Обе ваших задачи лежат в классе $P$(Вы это доказали), а значит и в $NP$.

это тролинг?

[Aritaborian]

esper369 в сообщении #1429170 писал(а):

это тролинг?

Нет. Это троллинг ;-) А вот со стороны Null — ни то ни другое.

[esper369]

Null в сообщении #1429168 писал(а):

Обе ваших задачи лежат в классе $P$(Вы это доказали), а значит и в $NP$.

Почему поиск по не сортированному списку принадлежит к $P$ классу, когда он к нему не принадлежит?

[Null]

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

[esper369]

Null в сообщении #1429177 писал(а):

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

но при этом такой алгоритм не будет быстрым - это будет алгоритм перебора

[Null]

Ну не будет быстрым и что? Все равно $P$

[esper369]

Null в сообщении #1429177 писал(а):

Все $P$ лежит в $NP$. $NP$ - это НЕ задачи не решаемые за полиномиальное время.

это правда
но класс $P$ отличается тем что алгоритмы в нем работают быстрее чем просто перебор
$NP$ класс - non-deterministic polynomial - задачи в нем недетерминированы

Моя гипотеза такая - что именно детерминированность определяет возможность существования $P$ класса.
В следствии чего в $NP$ классе не возможно полиноминальное ускорение по определению.

[Null]

esper369 в сообщении #1429180 писал(а):

но класс $P$ отличается тем что алгоритмы в нем работают быстрее чем просто перебор
$NP$ класс - non-deterministic polynomial - задачи в нем недетерминированы

Это неправда.

[arseniiv]

esper369 в сообщении #1429180 писал(а):

но класс $P$ отличается тем что алгоритмы в нем работают быстрее чем просто перебор
$NP$ класс - non-deterministic polynomial - задачи в нем недетерминированы

Нет, не так. В класс P входит то, что вычисляется на детерминированной машине Тьюринга за полиномиальное время, и в класс NP входит то, что вычисляется на недетерминированной машине Тьюринга за полиномиальное время.

-- Сб дек 07, 2019 19:04:26 --

Притом что значит «задача (не)детерминированна», вообще надо сначала определить.

[esper369]

arseniiv в сообщении #1429183 писал(а):

esper369 в сообщении #1429180 писал(а):

но класс $P$ отличается тем что алгоритмы в нем работают быстрее чем просто перебор
$NP$ класс - non-deterministic polynomial - задачи в нем недетерминированы

Нет, не так. В класс P входит то, что вычисляется на детерминированной машине Тьюринга за полиномиальное время, и в класс NP входит то, что вычисляется на недетерминированной машине Тьюринга за полиномиальное время.

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

[arseniiv]

Если это возражение, то на что и в чём именно оно заключается? Всем будет лучше, если вы будете стараться выражаться яснее.

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

-- Сб дек 07, 2019 19:47:54 --

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

[esper369]

...Продолжу.
Возьмем задачу о сумме подмножеств.
У нас есть $N$ чисел и $2^N$ комбинаций этих чисел.
Нам нужно среди этих комбинаций найти одну удовлетворяющую определенному условию (равенству числу)путь это будет число $M$.

Можно свести эту задачу к не сортированному списку, для этого избавимся от всех чисел:
Для этого мы берем первое число $X_1$ и делим задачу на 2 под задачи:
1)В первой подзадаче мы будем использовать первое число - то есть мы его вычтем из $M$ - Условие у нас будет равно $M - X_1$.
2)Во второй подзадаче мы не будем использовать первое число. И поэтому условие так и остается равенство $ M$.
Таким образом мы избавились от числа $X_1$ В этих двух случаях.
Проделав то же самое для остальных $N$ чисел мы получим не сортированный список из $2^N$ позиций.
И задача о сумме подмножеств сведется к поиску одного верного равенства из не сортированного списка равенств.

Теперь о задаче поиска по не сортированному списку.. Для этого представим другую задачу:

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

Точно так же в задаче о сумме подмножеств - мы не будем знать чему будет равна сумма нескольких чисел пока её не посчитаем.
Мы не будем знать точный ответ пока не посчитаем все суммы. Так как каждая из них может удовлетворять равенству.

...

arseniiv в сообщении #1429188 писал(а):

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

Ну то есть вопрос равенства $P$ $NP$ можно свести к вопросу: "возможно ли существование недетерминированной машины Тьюринга?" ??
пожалуй подумаю над этим...