Reducción de tablas de verdad

En la teoría de la computabilidad , una reducción de tabla de verdad es un tipo de reducción de un problema de decisión.${\displaystyle A}$a un problema de decisión${\displaystyle B}$Para resolver un problema en${\displaystyle A}$, la reducción describe la respuesta a${\displaystyle A}$como una fórmula booleana o tabla de verdad de un número finito de consultas a${\displaystyle B}$.

Las reducciones de tabla de verdad están relacionadas con las reducciones de Turing y son estrictamente más débiles. (Es decir, no toda reducción de Turing entre conjuntos puede realizarse mediante una reducción de tabla de verdad, pero toda reducción de tabla de verdad puede realizarse mediante una reducción de Turing). Una reducción de Turing de un conjunto B a un conjunto A calcula la pertenencia de un único elemento en B formulando preguntas sobre la pertenencia de varios elementos en A durante el cálculo; puede determinar de forma adaptativa qué preguntas formula en función de las respuestas a preguntas anteriores. En cambio, una reducción de tabla de verdad o una reducción de tabla de verdad débil debe presentar todas sus (un número finito de) consultas al oráculo simultáneamente. En una reducción de tabla de verdad, la reducción también proporciona una fórmula booleana (una tabla de verdad) que, al recibir las respuestas a las consultas, producirá la respuesta final de la reducción.

Las reducciones de tablas de verdad aparecen en un artículo de Emil Post publicado en 1944. ^{[ 1 ]}

Una reducción de tabla de verdad débil es aquella en la que la reducción utiliza las respuestas del oráculo como base para cálculos posteriores, que pueden depender de las respuestas dadas, pero no necesariamente plantear preguntas adicionales al oráculo. Se denomina así porque debilita las restricciones impuestas a una reducción de tabla de verdad y proporciona una clasificación de equivalencia más débil; por lo tanto, una "reducción de tabla de verdad débil" puede ser más potente que una reducción de tabla de verdad como "herramienta" y realizar una reducción que no es posible con una tabla de verdad. De forma equivalente, una reducción de tabla de verdad débil es una reducción de Turing cuyo uso está limitado por una función computable . Por esta razón, a veces se las denomina reducciones de Turing limitadas (bT) en lugar de reducciones de tabla de verdad débiles (wtt).

Como toda reducción de tabla de verdad es una reducción de Turing, si A es reducible a B mediante tabla de verdad ( A ≤ _tt B ), entonces A también es reducible a B mediante Turing ( A ≤ _T B ). Considerando también la reducibilidad uno a uno, la reducibilidad muchos a uno y la reducibilidad débil de tabla de verdad,

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

o dicho de otro modo, la reducibilidad uno a uno implica la reducibilidad muchos a uno, que implica la reducibilidad de la tabla de verdad, que a su vez implica la reducibilidad débil de la tabla de verdad, que a su vez implica la reducibilidad de Turing.

Además, A es reducible a B mediante una tabla de verdad si y solo si A es reducible a B mediante una función total en${\displaystyle 2^{\omega }}$. La dirección hacia adelante es trivial. Para la dirección inversa supongamos${\displaystyle \Gamma }$es un funcional totalmente computable. Para construir la tabla de verdad para calcular A ( n ), simplemente busque un número m tal que para todas las cadenas binarias${\displaystyle \sigma }$de longitud m ,${\displaystyle \Gamma ^{\sigma }(n)}$converge. Tal m debe existir por el lema de Kőnig ya que${\displaystyle \Gamma }$debe ser total en todos los caminos a través de${\displaystyle 2^{<\omega }}$Dado tal m, es sencillo encontrar la tabla de verdad única que da${\displaystyle \Gamma ^{\sigma }(n)}$cuando se aplica a${\displaystyle \sigma }$. La dirección hacia adelante falla para la reducibilidad débil de la tabla de verdad.

• H. Rogers, Jr. , 1967. La teoría de las funciones recursivas y la computabilidad efectiva , segunda edición, 1987, MIT Press. ISBN 0-262-68052-1(tapa blanda), ISBN 0-07-053522-1