Может ли аффинное лямбда-исчисление решить любую проблему в P?

В разделе «Расширенные темы по типам и языкам программирования» в главе, посвященной системам субструктурных типов, упоминается, что «тщательно разработанное» аффинное лямбда-исчисление с рекурсивным комбинатором для списков может вводить только те термины, которые имеют полиномиальное время выполнения (это не представить доказательства в силу сложности). Это было бы очень интересно, если бы мы могли также решить каждую проблему в P. Я мог бы попытаться найти решение P-полной задачи, используя представленное исчисление, я не уверен, что это действительно что-то докажет. Мне кажется, это не значит, что он может предварительно преобразовать все сокращения, необходимые для использования решения для P-полной задачи (хотя это действительно кажется вероятным).

Если неизвестно, что аффинное лямбда-исчисление способно точно решить проблемы в P, существует ли какое-либо известное исчисление, которое может точно решить проблемы в P?

cc.complexity-theory type-theory lambda-calculus Джейк
источник

Извините за мое невежество, но каков пример неполной задачи

и, что более важно, какое понятие сокращения вы используете?

P

$P$

Андрей Бауэр

Я нашел некоторые в Википедии: en.wikipedia.org/wiki/P-complete#P-complete_problems . Интерес представляет проблема значения схемы и рога-SAT. Линейное программирование, по-видимому, также является

полным. Эти слайды описывают проблему со значением схемы достаточно хорошо cs.cornell.edu/courses/CS6820/2012sp/Handouts/cvp.pdf . Кажется, что используются либо сокращения

либо

, причем сокращения

слабее, чем сокращения

Я был бы доволен либо; Я не уверен, какие последствия использования

против

точно.

P

$P$

L

$L$

N C

$NC$

L

$L$

N C

$NC$

L

$L$

N C

$NC$

Джейк

Существуют линейные языки, которые являются полными для P. Интересно, что они обычно полны для задач, но не для алгоритмов. То есть, вы можете написать программу на много времени для каждой задачи в P, но не каждый алгоритм на основе времени может быть выражен.

Нил Кришнасвами

Будет ли это утверждение примерно эквивалентно «они обычно полны для P, но не для FP»? Также, если бы вы могли привести несколько примеров, это был бы удивительный ответ.

Джейк

Нил Кришнасвами, можете ли вы дать ссылку? Это звучит интересно.

Матеус де Оливейра Оливейра

Ответы:

Изменить: мое предположение в первом абзаце ниже неверно! Уго Даль Лаго указал мне на более позднюю статью Мартина Хофмана (вышедшую в POPL 2002), о которой я не знал, показывая (как следствие более общих результатов), что система из книги ATTPL на самом деле завершена для ( несмотря на неспособность вычислить каждую функцию в ). Так что, к моему удивлению, ответ на главный вопрос - да. $\mathsf P$ $\mathsf{FP}$

$\mathsf P$ $\mathsf{FP}$ , что исключает множество функций polytime. Похоже, что это также серьезно ограничивает размер ленты машин Тьюринга, которые вы можете смоделировать на этом языке. В статье Хофманн показывает, что вы можете кодировать линейные вычисления в пространстве; я предполагаю, что вы не сможете сделать гораздо больше, т. е. класс, соответствующий этой системе, примерно равен задачам, решаемым одновременно в многопоточном и линейном пространстве.

$\lambda$ $\mathsf P$ $\lambda$ $\mathsf{FP}$ $\lambda$ 318 (1-2): 163-180, 2004). Системы типов, возникающие из этих двух последних логических систем и обеспечивающие завершение многопоточности (при этом сохраняя полноту), можно найти в:

Патрик Бейло, Казушиге Теруи. Типы света для вычисления полиномиального времени в лямбда-исчислении. Информация и вычисления 207 (1): 41-62, 2009.

Марко Габоарди, Симона Рончи Делла Рокка. От легкой логики до типовых заданий: тематическое исследование. Logic Journal of IGPL 17 (5): 499-530, 2009.

Вы найдете много других ссылок в этих двух статьях.

$\lambda$ $\Phi$ $P:\texttt{string}\rightarrow\texttt{bool}$

$\Phi(P)$ $P$ $\mathsf P$

$L\in\mathsf P$ $P$ $L$ $\Phi(P)$

$\Phi$ $L$ $\mathsf P$ $P$ $L$ $\Phi(P)$ $P'$ $L$ $\Phi(P')$ $P'$ $P$ $\Phi$ $L$ $P$ $\Phi$

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

Уго Дал Лаго, Марко Габоарди. Линейно-зависимые типы и относительная полнота. Логические методы в информатике 8 (4), 2011.

Дамиано Мазза
источник

Я не понимаю, что вы пытаетесь сказать во второй половине. Исходя из вашего описания, существует синтаксическая трансформация машин Тьюринга с многократной синхронизацией в F-программы, решающие ту же проблему. Насколько я вижу, это лучшее, на что можно надеяться при переводе с одной модели вычисления на другую.

Эмиль Йержабек

Φ

$\Phi$

N a t := \forall X . (X \to X) \to X \to X

$Nat:=\forall X.(X\rightarrow X)\rightarrow X\rightarrow X$

λ m^{N a t} . λ n^{N a t} . Λ X . λ s^{X \to X} . m X (n X s)

$\lambda m^{Nat}.\lambda n^{Nat}.\Lambda X.\lambda s^{X\rightarrow X}.mX(nXs)$

f o r

$\mathtt{for}$

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

Джейк