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

В теории вычислимости редукция таблицы истинности — это редукция одного набора натуральных чисел к другому. ^{[ требуется разъяснение ]} Как «инструмент» он слабее, чем редукция Тьюринга , поскольку не всякая редукция Тьюринга между наборами может быть выполнена с помощью редукции таблицы истинности, но каждая редукция таблицы истинности может быть выполнена с помощью редукции Тьюринга. По той же причине говорят, что это более сильная сводимость, чем сводимость по Тьюрингу, потому что она подразумевает сводимость по Тьюрингу. Слабое сокращение таблицы истинностиродственный тип редукции, названный так потому, что он ослабляет ограничения, накладываемые на редукции таблицы истинности, и обеспечивает более слабую классификацию эквивалентности; как таковая, «слабая редукция таблицы истинности» на самом деле может быть более мощной, чем редукция таблицы истинности, как «инструмент», и выполнять редукцию, которую невозможно выполнить с помощью таблицы истинности.

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

Эквивалентно, слабая редукция таблицы истинности - это редукция Тьюринга, для которой использование редукции ограничено вычислимой функцией . По этой причине их иногда называют ограниченными редукциями Тьюринга (bT), а не слабыми редукциями таблицы истинности (wtt).

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

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

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