Reducción de la tabla de la verdad

En la teoría de la computabilidad , una reducción de la 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 tabla de verdad, pero cada reducción de tabla de verdad puede 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 la reducibilidad de Turing. Una reducción débil de la tabla de verdades un tipo de reducción relacionado que 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; como tal, una "reducción de tabla de verdad débil" en realidad puede ser más poderosa que una reducción de tabla de verdad como una "herramienta", y realizar una reducción que no es ejecutable por tabla de verdad.

Una reducción de Turing de un conjunto B a un conjunto A calcula la pertenencia de un solo elemento en B haciendo preguntas sobre la pertenencia de varios elementos en A durante el cálculo; puede determinar de forma adaptativa qué preguntas hace basándose en las respuestas a preguntas anteriores. Por el contrario, una reducción tabla de verdad o una débil reducción tabla de verdad deben presentar todos sus (un número finito) de Oracle consultas al mismo tiempo. En una reducción de tabla de verdad, la reducción también da una función booleana(una tabla de verdad) que, cuando se 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 el cálculo adicional que puede depender de las respuestas dadas, pero puede que no plantee más preguntas al oráculo.

De manera equivalente, una reducción de tabla de verdad débil 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 les llama 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 la tabla de verdad reducible a B ( A ≤ _tt B ), entonces A también es Turing reducible 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, 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 Turing reducible a B a través de un total funcional en . La dirección de avance es trivial y para la dirección de retroceso supongamos que es un total funcional computable. Para construir la tabla de verdad para calcular A (n) simplemente busque un número m tal que todas las cadenas binarias de longitud m converjan. Tal m debe existir según el lema de Kőnig, ya que debe ser total en todos los caminos . Dada tal m , es una cuestión sencilla encontrar la tabla de verdad única que da ${\ Displaystyle 2 ^ {\ omega}}$ ${\ Displaystyle \ Gamma}$ ${\ Displaystyle \ sigma}$ ${\ Displaystyle \ Gamma ^ {\ sigma} (n)}$ ${\ Displaystyle \ Gamma}$ ${\ Displaystyle 2 ^ {<\ omega}}$ ${\ Displaystyle \ Gamma ^ {\ sigma} (n)}$ cuando se aplica a . La dirección hacia adelante falla por una reducción débil de la tabla de verdad. ${\ Displaystyle \ sigma}$