О критериях постановки задачи разрешения (P vs NP)

[Random_account]

Здравствуйте. Хочу проверить на корректность свою формализацию интуитивного понимания разницы между «проверкой» и «решением» в теории сложности, а также уточнить границы определения «задачи разрешения».

На основе анализа я выделил следующие критерии, при которых объект можно считать корректно поставленной задачей разрешения:

1. Наличие входа: Должна быть задана конечная строка (входные данные).
2. Наличие однозначного предиката: Должно существовать свойство, которое можно однозначно проверить (истина или ложь).
3. Критерий ответа: Алгоритм должен давать ответ за конечное число шагов, зависящее от длины входа.

Отсюда вытекают два вопроса, которые я хочу прояснить:

Вопрос 1: Граница между «некорректной постановкой» и «неразрешимой задачей».
Если у нас есть вопрос, не имеющий однозначной постановки (например, запрос на подтверждение «5 — число?», где нет строгого предиката), является ли это «неразрешимой задачей» или это объект, который вообще находится вне области определения задачи разрешения (то есть просто некорректно поставленный вопрос, где понятие сложности не определено)?

Вопрос 2: Статус тривиальных задач.
Если задача имеет сложность O(1) (то есть число шагов не растет с размером входа), считается ли она частью класса P, или она выпадает из рассмотрения теории сложности, так как не отражает асимптотическое поведение?

Я понимаю, что интуиция «скорее P не равно NP» не заменяет доказательства, и за 50 с лишним лет профессионалы не смогли этого доказать. Я не претендую на решение задачи тысячелетия. Моя цель — строго зафиксировать терминологические границы и убедиться, что моя логика не содержит формальных ошибок.

Буду благодарен за указание на неточности в определениях и ссылки на формальные источники.

[mihaild]

Random_account в сообщении #1737725 писал(а):

Если задача имеет сложность O(1) (то есть число шагов не растет с размером входа), считается ли она частью класса P, или она выпадает из рассмотрения теории сложности, так как не отражает асимптотическое поведение?

Считается. Есть два подхода к определению (ничего содержательного от этого не зависит, только немного техники) - по одному таких задач вообще не бывает.

Random_account в сообщении #1737725 писал(а):

Моя цель — строго зафиксировать терминологические границы и убедиться, что моя логика не содержит формальных ошибок.

Для этого лучше сразу открыть имеющиеся публикации, а не пытаться на коленке придумать что-то своё.
Строгая формулировка есть, например, на сайте институа Клэя https://www.claymath.org/wp-content/upl ... /pvsnp.pdf (упражнение на понимание: по их определениям, есть ли языки, проверяющиеся за $O(1)$?).

Random_account в сообщении #1737725 писал(а):

Буду благодарен за указание на неточности в определениях

Пока что определений у Вас я не увидел.

[Random_account]

Спасибо за ссылку на статью Кука и за наводку. По поводу Вашего вопроса (есть ли языки, проверяющиеся за O(1)) — я попробовал разобрать это на примерах.

Согласно определению из раздела 1 (машина Тьюринга работает за время T_M(n) меньше или равно n в степени k плюс k), если k равно 0, то время работы константно, то есть O(1).

Пример тривиальной задачи: пусть алфавит состоит из нуля и единицы, а язык L — это множество строк, где первый символ равен единице. Машина Тьюринга читает первый символ и сразу останавливается (переход в допускающее или отвергающее состояние). Число шагов равно одному, оно не зависит от длины входа n. Значит, k равно 0, и этот язык принадлежит классу P.

Пример настоящей задачи: язык палиндромов. Машина должна пройти от начала до конца, запомнить строку и сравнить с обратной. Число шагов пропорционально n, значит сложность O(n), то есть k равно 1. Это тоже класс P.

Теперь про проверку в NP. Проверочное соотношение R(w, y) должно работать за полиномиальное время. Если проверка идет за O(1), это значит, что мы проверяем только константное число символов сертификата y. Но если мы можем проверить язык за O(1), то мы можем и решить его за O(1). Следовательно, такой язык автоматически принадлежит классу P.

Получается, что языки, проверяющиеся за O(1), не выпадают из теории, а просто являются вырожденным (тривиальным) случаем класса P.

Правильно ли я понял логику из статьи Кука?

[mihaild]

Random_account в сообщении #1737742 писал(а):

Машина должна пройти от начала до конца, запомнить строку и сравнить с обратной. Число шагов пропорционально n, значит сложность O(n), то есть k равно 1. Это тоже класс P.

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

Random_account в сообщении #1737742 писал(а):

Правильно ли я понял логику из статьи Кука?

В целом пока ошибок не вижу.

[Geen]

Random_account в сообщении #1737742 писал(а):

Но если мы можем проверить язык за O(1), то мы можем и решить его за O(1).

Это откуда следует?

[makxsiq]

Geen в сообщении #1737782 писал(а):

Random_account в сообщении #1737742 писал(а):

Но если мы можем проверить язык за O(1), то мы можем и решить его за O(1).

Это откуда следует?

Имхо если язык можно проверить за О(1), то ключ не зависит от размера входных данных, следовательно и найти этот ключ можно перебором за О(1).