Редукция таблицы истинности

В теории вычислимости редукция таблицы истинности — это тип редукции от задачи принятия решения к задаче принятия решения . Чтобы решить задачу в , редукция описывает ответ на как булеву формулу или таблицу истинности некоторого конечного числа запросов к .${\displaystyle А}$${\displaystyle Б}$${\displaystyle А}$${\displaystyle А}$${\displaystyle Б}$

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

Редукция таблицы истинности появилась в статье Эмиля Поста, опубликованной в 1944 году. ^[1]

Этот раздел нуждается в расширении . Вы можете помочь, дополнив его. ( Апрель 2024 )

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

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

${\displaystyle A\leq _{1}B\Стрелка вправо A\leq _{m}B\Стрелка вправо A\leq _{tt}B\Стрелка вправо A\leq _{wtt}B\Стрелка вправо A\leq _{T}B}$,

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

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

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

Эта статья, связанная с математической логикой, является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е