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

[arseniiv]

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

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

Нет, нельзя свести. И детерминированная МТ, и недетерминированная МТ существуют как математические конструкции и не существуют никаким другим образом без уточнения, что будет значить это существование.

[mihaild]

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

Можно свести эту задачу к не сортированному списку

Сформулируйте точно, что такое "задача поиска по несортированному списку" - в каком виде выдается список?
Если он дается на вход полностью - то эта задача принадлежит $P$. Если дается метод генерации - то в зависимости от деталей эта задача может быть сколь угодно сложной вплоть до неразрешимости.

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

Мы не будем знать точный ответ пока не посчитаем все суммы

Непонятно, что это значит, но в любом случае задача SUBSET-SUM для $n$ чисел из $k$ битов решается за время $O(2^{n/2}\cdot poly(n, k))$ ($poly(n, k)$ - сложение $O(n)$ чисел, начиная с чисел из $O(k)$ разрядов), а различных сумм может быть до $2^n$.

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

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

Гипотеза: ничего осмысленного из этого набора слов вытащить не удастся.

[Lia]

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

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

esper369
Это вопрос или аннотация?

[epros]

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

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

Конечно же недетерминированной машины Тьюринга не существует, как и детерминированной, ибо в природе не бывает устройств с бесконечной лентой. На самом деле это математические абстракции.

Но вопрос сводится вовсе не к этому.

[Евгений Машеров]

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

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

Потому, что принадлежит. n это полином первой степени от n.

[Евгений Машеров]

Мне кажется, Вы путаете "неформальные пояснения" с определением.
"P - быстрорешаемые, а NP - медленнорешаемые задачи" это пояснение, притом, вообще говоря, неверное. Хотя во многих случаях это так - но могут быть полиномиальные алгоритмы, слишком медленные для практического применения, и алгоритмы экспоненциальной в общем случае сложности, достаточно быстро решающие практически возникающие задачи (скажем, та же задача коммивояжёра известным алгоритмом ветвей и границ для случайно сгенерированной матрицы решается за время, приближаемое полиномом менее чем четвёртой степени, экспоненциальность на специально подобранных матрицах).
"NP - перебор, P - без полного перебора" это пояснение, притом, вообще говоря, неверное. Полный перебор из n вариантов выполняется за n шагов. Вот если перебирать все подмножества из множества мощностью n...
Ну и Ваше понимание детерминированности несколько... эээ... нетрадиционно.

[Lia]

Lia в сообщении #1429216 писал(а):

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

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

esper369
Это вопрос или аннотация?

Разъяснений не поступило, а содержание темы говорит о том, что это скорее вопрос. Переношу в ПРР.

[Lia]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: см. выше.