Сокращение таблицы истинности

В теории вычислимости редукция таблицы истинности - это тип редукции проблемы решения. $A$ к проблеме решения $B$. Чтобы решить проблему в $A$, сокращение описывает ответ на $A$ как булева формула или таблица истинности некоторого конечного числа запросов к $B$.

Сокращения таблицы истинности связаны с сокращениями Тьюринга и строго слабее. (То есть не каждое сокращение по Тьюрингу между наборами может быть выполнено путем сокращения таблицы истинности, но каждое сокращение таблицы истинности может быть выполнено путем сокращения по Тьюрингу.) Сведение по Тьюрингу из набора B в набор A вычисляет членство один элемент в B, задавая вопросы о членстве различных элементов в A во время вычислений; он может адаптивно определять, какие вопросы задавать, на основе ответов на предыдущие вопросы. Напротив, редукция таблицы истинности или слабая редукция таблицы истинности должна представлять все свои (конечное множество) запросы оракула одновременно. При сокращении таблицы истинности сокращение также дает логическую формулу (таблицу истинности), которая при получении ответов на запросы дает окончательный ответ сокращения.

Слабые сокращения таблицы истинности

Слабая редукция таблицы истинности — это такая редукция, при которой ответы оракула используются в качестве основы для дальнейших вычислений, которые могут зависеть от данных ответов, но не могут задавать дополнительные вопросы оракулу. Он назван так потому, что ослабляет ограничения, налагаемые на сокращение таблицы истинности, и обеспечивает более слабую классификацию эквивалентности; как таковое, «слабое сокращение таблицы истинности» на самом деле может быть более мощным, чем сокращение таблицы истинности, в качестве «инструмента» и выполнять сокращение, которое невозможно выполнить с помощью таблицы истинности. Эквивалентно, слабая редукция таблицы истинности — это редукция Тьюринга, для которой использование редукции ограничено вычислимой функцией . По этой причине их иногда называют ограниченными редукциями Тьюринга (bT), а не слабыми редукциями таблицы истинности (wtt).

Характеристики

Поскольку каждая редукция таблицы истинности является редукцией по Тьюрингу, если является таблицей истинности, сводимой к B ( A ≤ _tt B ), то A также сводится по Тьюрингу к B ( A ≤ _TB A ). Учитывая также сводимость «одна-единица», сводимость «многие-единицы» и слабую сводимость к таблице истинности,

$A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B$,

или, другими словами, сводимость «один к одному» подразумевает сводимость «многие к одному», что подразумевает сводимость к таблице истинности, что, в свою очередь, подразумевает слабую сводимость к таблице истинности, что, в свою очередь, подразумевает сводимость по Тьюрингу.

Более того, A является таблицей истинности, сводимой к B тогда и только тогда, когда A сводимо по Тьюрингу к B через полный функционал на $2^{\omega }$. Прямое направление тривиально, а для обратного направления предположим, что $\Gamma$ — полный вычислимый функционал. Чтобы построить таблицу истинности для вычисления A ( n ), просто найдите число m такое, что для всех двоичных строк $\sigma$ длины м $\Gamma ^{\sigma }(n)$ сходится. Такое m должно существовать по лемме Кенига, поскольку $\Gamma$ должно быть тотальным на всех путях через $2^{<\omega }$. Учитывая такое m, несложно найти единственную таблицу истинности, которая дает $\Gamma ^{\sigma }(n)$ применительно к $\sigma$. Прямое направление не удается из-за слабой сводимости к таблице истинности.

Ссылки

• Х. Роджерс-младший , 1967. Теория рекурсивных функций и эффективная вычислимость , второе издание, 1987, MIT Press. ISBN   0-262-68052-1 (мягкая обложка), ISBN   0-07-053522-1