En teoría de la computabilidad , una reducción de tabla de verdad es una reducción de un conjunto de números naturales a otro. [ aclaración necesaria ] Como "herramienta", es más débil que la reducción de Turing , ya que no todas las reducciones de Turing entre conjuntos pueden realizarse mediante una reducción de la tabla de verdad, pero todas las reducciones de la tabla de verdad pueden realizarse mediante una reducción de Turing. Por la misma razón se dice que es una reducibilidad más fuerte que la reducibilidad de Turing, porque implica reducibilidad de Turing. Una reducción débil de la tabla de verdad es un tipo relacionado de reducción que se llama así porque debilita las restricciones impuestas a una reducción de la tabla de verdad y proporciona una clasificación de equivalencia más débil; como tal, una "reducción débil de la tabla de verdad" puede en realidad ser más poderosa que una reducción de la tabla de verdad como "herramienta" y realizar una reducción que no se puede realizar mediante una tabla de verdad.
Una reducción de Turing de un conjunto B a un conjunto A calcula la pertenencia de un único elemento a B haciendo preguntas sobre la pertenencia de varios elementos a A durante el cálculo; puede determinar de forma adaptativa qué preguntas formula basándose en las respuestas a preguntas anteriores. Por el contrario, una reducción de tabla de verdad o una reducción de tabla de verdad débil debe presentar todas sus (finitas) consultas de Oracle al mismo tiempo. En una reducción de tabla de verdad, la reducción también proporciona una función booleana (una tabla de verdad) que, cuando se le den las respuestas a las consultas, producirá la respuesta final de la reducción. En una reducción débil de la tabla de verdad, la reducción utiliza las respuestas del oráculo como base para cálculos adicionales que pueden depender de las respuestas dadas pero que no pueden plantear más preguntas al oráculo.
De manera equivalente, una reducción débil de la tabla de verdad es una reducción de Turing para la cual el uso de la reducción está limitado por una función computable . Por esta razón, a veces se las denomina reducciones de Turing acotadas (bT) en lugar de reducciones débiles de tabla de verdad (wtt).
Como toda reducción de la tabla de verdad es una reducción de Turing, si A es reducible por tabla de verdad a B ( A ≤ tt B ), entonces A también es reducible de Turing a B ( A ≤ T B ). Considerando también la reducibilidad uno uno, la reducibilidad muchos uno y la reducibilidad débil de la tabla de verdad,
o en otras palabras, la reducibilidad uno uno implica reducibilidad muchos uno, lo que implica reducibilidad de tabla de verdad, que a su vez implica reducibilidad de tabla de verdad débil, que a su vez implica reducibilidad de Turing.
Además, A es reducible por tabla de verdad a B si A es reducible por Turing a B mediante un funcional total en . La dirección de avance es trivial y para la dirección inversa supongamos que es un funcional total computable. Para construir la tabla de verdad para calcular A(n), simplemente busque un número m tal que para todas las cadenas binarias de longitud m converja. Tal m debe existir según el lema de Kőnig ya que debe ser total en todos los caminos que pasan por . Dado tal m, es sencillo encontrar la única tabla de verdad que da cuando se aplica a . La dirección hacia adelante falla por una reducibilidad débil de la tabla de verdad.
