En ciencia computacional teórica, la dualización monótona es un problema computacional que consiste en construir el dual de una función monótona booleana. También se pueden formular problemas equivalentes como la construcción del hipergrafo transversal de un hipergrafo dado, la enumeración de todos los conjuntos colindantes mínimos de una familia de conjuntos o la enumeración de todos los conjuntos de recubrimiento mínimos de una familia de conjuntos. Estos problemas se pueden resolver en tiempo casi polinómico con el tamaño combinado de su entrada y salida, pero si se pueden resolver en tiempo polinómico sigue siendo un problema abierto.
Definiciones Una función booleana toma como entrada la asignación del valor de verdad a sus argumentos y produce como salida otro valor de verdad. Es monótona cuando cambiar un argumento de falso a verdadero no puede cambiar la salida de verdadero a falso. Toda función booleana monótona se puede expresar como una expresión booleana utilizando únicamente la disyunción lógica ("o") y la conjunción lógica ("y"), sin utilizar la negación lógica ("no"). Dicha expresión se denomina expresión booleana monótona. Cada expresión booleana monótona describe una función booleana monótona.
Pueden existir muchas expresiones diferentes para la misma función. Entre ellas se encuentran dos expresiones especiales: la forma normal conjuntiva y la forma normal disyuntiva. Para funciones monótonas, estas dos formas especiales también pueden restringirse a monótonas:
La forma normal conjuntiva de una función monótona expresa la función como una conjunción ("y") de cláusulas, cada una de las cuales es una disyunción ("o") de algunas de las variables. Una cláusula puede aparecer en la forma normal conjuntiva si es verdadera siempre que la función general lo sea; en este caso, se denomina implicada, porque la verdad de la función implica la verdad de la cláusula. Esta expresión puede hacerse canónica restringiéndola al uso exclusivo de implicadas primas, es decir, las implicadas que utilizan un conjunto mínimo de variables. La forma normal conjuntiva que utiliza solo implicadas primas se denomina CNF prima.
La forma normal disyuntiva de una función monótona expresa la función como una disyunción ("o") de cláusulas, cada una de las cuales es una conjunción ("y") de variables. Una conjunción puede aparecer en la forma normal disyuntiva si es falsa siempre que la función general sea falsa; en este caso, se denomina implicante, porque su veracidad implica la veracidad de la función. Esta expresión puede hacerse canónica restringiéndola al uso exclusivo de implicantes primos, aquellos que utilizan un conjunto mínimo de variables. La forma normal disyuntiva que utiliza únicamente implicantes primos se denomina DNF prima.
El dual de una función booleana se obtiene negando todas sus variables, aplicando la función y, a continuación, negando el resultado. El dual del dual de cualquier función booleana es la función original. El dual de una función monótona es monótona. Si se da una expresión booleana monótona, al reemplazar todas las conjunciones por disyunciones se obtiene otra expresión booleana monótona para la función dual, lo que se deduce de las leyes de De Morgan. Sin embargo, esto transformará la forma normal conjuntiva en una forma normal disyuntiva, y viceversa, lo cual puede ser indeseable. La dualización monótona consiste en encontrar una expresión para la función dual sin cambiar su forma, o, equivalentemente, en convertir una función de una forma normal a la forma dual.
Como problema funcional, la dualización monótona se puede expresar de las siguientes maneras equivalentes:
Dada una expresión CNF (prima), construir una expresión CNF (prima) para la función dual. Convertir la expresión CNF (prima) de una función en la expresión DNF (prima) para la misma función, o viceversa. Construir el "hipergrafo transversal" de un hipergrafo dado. Este es un hipergrafo en el mismo conjunto de vértices que tiene una hiperarista para cada subconjunto mínimo de vértices que toca todas las aristas del hipergrafo dado. Dada una familia de conjuntos, generar todos los conjuntos contiguos mínimos de la familia. Se trata de conjuntos de elementos que incluyen al menos un elemento de cada conjunto y no tienen ningún subconjunto propio con la misma propiedad. Si los conjuntos de la familia dada se interpretan como hiperaristas en un hipergrafo, sus conjuntos mínimos coincidentes son las hiperaristas del hipergrafo transversal. Dada una familia de conjuntos, generar todos los conjuntos de recubrimiento mínimos de la familia. Una cobertura de conjunto es una subfamilia con la misma unión que toda la familia. Si los conjuntos de la familia dada se interpretan como vértices en un hipergrafo, y cada elemento de los conjuntos se interpreta como una hiperarista incidente a los conjuntos que contienen ese elemento, entonces las coberturas de conjunto mínimas son las hiperaristas del hipergrafo transversal.
Otra versión del problema puede formularse como un problema de "aprendizaje exacto" en teoría del aprendizaje computacional: dado acceso a una subrutina para evaluar una función booleana monótona, reconstruir las representaciones CNF y DNF de la función, utilizando un pequeño número de evaluaciones de la función. Sin embargo, para analizar la complejidad de este problema, es crucial que se generen tanto las representaciones CNF como DNF. Si solo se genera la representación CNF de una función monótona desconocida, según la teoría de la información se deduce que el número de evaluaciones de funciones a veces debe ser exponencial en los tamaños combinados de entrada y salida. Esto se debe a que (para asegurar la respuesta correcta) el algoritmo debe evaluar la función al menos una vez para cada implicado primo y al menos una vez para cada implicante primo, pero este número de evaluaciones puede ser exponencialmente mayor que el número de implicados primos por separado.
También es posible expresar una variante del problema de dualización monótona como un problema de decisión, con una respuesta booleana:
Comprobar si dos expresiones CNF primas representan funciones duales. Comprobar si una expresión CNF prima y una expresión DNF prima representan la misma función.
Se trata de un problema no resuelto si la dualización monótona tiene un algoritmo de tiempo polinómico (en cualquiera de estas formas equivalentes). Los algoritmos más rápidos conocidos se ejecutan en tiempo casi polinómico. El tamaño de la salida de los problemas de dualización y aprendizaje exacto puede ser exponencialmente grande, como una función del número de variables o del tamaño de la entrada. Por ejemplo, un grafo de vértices que consiste en triángulos disjuntos tiene hiperaristas en su hipergrafo transversal. Por lo tanto, lo que se desea para estos problemas es un algoritmo sensible a la salida, uno que tome una pequeña cantidad de tiempo por cláusula de salida. Las formulaciones de decisión, dualización y aprendizaje exacto del problema son todas computacionalmente equivalentes, en el siguiente sentido: cualquiera de ellas puede ser resuelta usando una subrutina para cualquier otro de estos problemas, con un número de llamadas a subrutinas que es polinómico en los tamaños combinados de entrada y salida de los problemas. Por lo tanto, si cualquiera de estos problemas pudiera ser resuelto en tiempo polinómico, todos los demás podrían también ser resueltos. Sin embargo, la mejor cota temporal conocida para estos problemas es en tiempo casi polinómico. Queda por resolver si pueden resolverse en tiempo polinómico.
Complejidad computacional Equivalencia de decisión, enumeración y aprendizaje exacto El problema de encontrar la expresión CNF prima para la función dual de una función monótona, dada como una fórmula CNF, se puede resolver hallando la expresión DNF para la función dada y luego dualizándola. Por lo tanto, encontrar la expresión CNF dual y la expresión DNF para la función dada (primaria) tienen la misma complejidad. Este problema también puede considerarse un caso especial de la formulación de aprendizaje exacto. A partir de una expresión CNF dada, es sencillo evaluar la función que expresa. Un algoritmo de aprendizaje exacto devolverá tanto la expresión CNF inicial como la expresión DNF deseada. Por lo tanto, la dualización no puede ser más difícil que el aprendizaje exacto.
También es sencillo resolver el problema de decisión dado un algoritmo para la dualización: dualizar la expresión CNF dada y luego comprobar si es igual a la expresión DNF dada. Por lo tanto, la investigación en esta área se ha centrado en la otra dirección de esta equivalencia: resolver el problema de aprendizaje exacto (o el problema de dualización) dada una subrutina para el problema de decisión.
describe el siguiente algoritmo para resolver el aprendizaje exacto mediante una subrutina de decisión:
Inicializar los conjuntos de cláusulas CNF y DNF primas identificadas hasta el momento, inicialmente vacías. Repetir los siguientes pasos: Utilizar el problema de decisión para comprobar si los conjuntos actuales de cláusulas CNF y DNF primas son duales y, de ser así, finalizar el algoritmo, devolviendo las cláusulas encontradas. Construir una asignación de verdad con las variables para las cuales el valor de la función no está obligado a ser verdadero ni falso por las cláusulas DNF primas conocidas. Esta construcción puede realizarse seleccionando valores para las variables una a una, utilizando en cada paso el problema de decisión para preservar la propiedad de que las cláusulas CNF y DNF no son duales cuando se restringen a la asignación de verdad elegida. Evaluar la función en esta asignación de verdad. Si es verdadera, intentar cambiar las variables una a una de verdaderas a falsas para encontrar una asignación de verdad mínima para la que la función siga evaluándose como verdadera. Esta asignación de verdad mínima corresponde a una cláusula DNF principal, aún no conocida; añadirla al conjunto de cláusulas conocidas. Simétricamente, si la función se evalúa como falsa, intentar cambiar las variables una a una de falsa a verdadera para encontrar una asignación de verdad máxima para la que la función aún se evalúe como falsa. Esta asignación de verdad máxima corresponde a una cláusula CNF principal, aún no conocida; añadirla al conjunto de cláusulas conocidas.
Cada iteración del bucle externo del algoritmo utiliza un número lineal de llamadas al problema de decisión para encontrar la asignación de verdad no forzada, utiliza un número lineal de evaluaciones de la función para encontrar un valor de función mínimo verdadero o máximo falso, y añade una cláusula a la salida. Por lo tanto, el número total de llamadas al problema de decisión y el número total de evaluaciones de la función es un polinomio del tamaño total de la salida.
Tiempo casi polinómico