Во введении и объяснении P и NP классы сложности часто даются через машину Тьюринга. Одной из моделей вычислений является лямбда-исчисление. Я понимаю, что все модели вычислений эквивалентны (и если мы можем ввести что-либо в терминах машины Тьюринга, мы можем представить это в терминах любой модели вычислений), но я никогда не видел объяснения идеи P и классов сложности NP через лямбда-исчисление , Кто-нибудь может объяснить понятия классов сложности P и NP без машины Тьюринга и только с помощью лямбда-исчисления в качестве модели вычисления.
36
Ответы:
Машины Тьюринга иλ калькуляция эквивалентны только по функциям N→N они могут определить.
С точки зрения вычислительной сложности они, кажется, ведут себя по-разному. Основная причина, по которой люди используют машины Тьюринга, а неλ калькуляцию, чтобы рассуждать о сложности, заключается в том, что использование λ калькулятора наивно ведет к нереалистичным мерам сложности, потому что вы можете свободно копировать термины (произвольного размера) за один этап β сокращения, например (λx.xxx)M→MMM. Другими словами, одиночные шаги восстановления в λ -калькулез - это паршивая модель затрат. Напротив, одиночные шаги сокращения машины Тьюринга работают отлично (в смысле того, чтобы быть хорошими предикторами реального времени выполнения программы).
Неизвестно, как полностью восстановить традиционную теорию сложности, основанную на машине Тьюринга, вλ вычислении. В недавнем (2014) прорыве Аккаттоли и Даль Лаго
удалось показать, что большим классам сложности времени, таким как P , NP и EXP может быть дана естественная формула λ вычисления. Но меньшие классы, такие как O(n2) или O(nlogn) не могут быть представлены с использованием методов Аккаттоли / Дал Лаго.
Как восстановить обычную космическую сложность, используяλ калькуляцию, неизвестно.
источник
Я вставляю часть ответа, который я написал для другого вопроса :
Существуют характеристики (как минимум) с помощью λ- исчисления.FP λ
источник
Я не знаю, отвечает ли это (часть) на ваш вопрос, но действительно есть альтернативные характеристики классов сложности (особенноP и NP ) в терминах логики (логика 1-го порядка, логика 2-го порядка и т. Д.).
Например, работа по Р. Fagin ( и др.) В этой области отличается (и имо может дать представление , связанное сP против NP вопроса и отношений с описательной и алгоритмической сложностью)
Некоторые дополнительные характеристики классов вычислительной сложности в терминах алгоритмической (колмогоровской-соломоновской) сложности можно найти (например) здесь и здесь .
источник