oráculo matroide

En matemáticas e informática, un oráculo matroide es una subrutina mediante la cual un algoritmo puede acceder a un matroide , una estructura combinatoria abstracta que puede utilizarse para describir las dependencias lineales entre vectores en un espacio vectorial o los árboles generadores de un grafo , entre otras aplicaciones.

El oráculo más utilizado de este tipo es un oráculo de independencia , una subrutina para comprobar si un conjunto de elementos de un matroide es independiente. También se han utilizado otros tipos de oráculos; algunos han demostrado ser más débiles que los oráculos de independencia, otros más fuertes y otros equivalentes en potencia computacional. ^{[ 1 ]}

Muchos algoritmos que realizan cálculos en matroides se han diseñado para tomar un oráculo como entrada, lo que les permite ejecutarse de manera eficiente sin modificaciones en muchos tipos diferentes de matroides y sin suposiciones adicionales sobre el tipo de matroid que están utilizando. Por ejemplo, dado un oráculo de independencia para cualquier matroid, es posible encontrar la base de peso mínimo del matroid aplicando un algoritmo voraz que agrega elementos a la base en orden ascendente según su peso, utilizando el oráculo de independencia para comprobar si cada elemento puede agregarse. ^{[ 2 ]}

En la teoría de la complejidad computacional , el modelo de oráculo ha dado lugar a cotas inferiores incondicionales que demuestran que ciertos problemas de matroides no pueden resolverse en tiempo polinomial, sin recurrir a supuestos no probados como el supuesto de que P ≠ NP . Entre los problemas que se ha demostrado que son difíciles de resolver de esta manera se incluyen comprobar si un matroide es binario o uniforme , o comprobar si contiene ciertos menores fijos . ^{[ 3 ]}

Aunque algunos autores han experimentado con representaciones informáticas de matroides que enumeran explícitamente todos los conjuntos independientes o todos los conjuntos base del matroide, ^{[ 4 ]} estas representaciones no son sucintas : un matroide con${\displaystyle n}$Los elementos pueden expandirse en una representación que ocupa espacio exponencialmente en${\displaystyle n}$De hecho, el número de matroides distintos en${\displaystyle n}$los elementos crecen exponencialmente de forma doble

${\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}$^{[ 5 ]}

de lo cual se deduce que cualquier representación explícita capaz de manejar todos los posibles matroides necesariamente usaría espacio exponencial. ^{[ 6 ]}

En cambio, los distintos tipos de matroides pueden representarse de forma más eficiente a partir de las estructuras que los definen: matroides uniformes a partir de sus dos parámetros numéricos, matroides gráficos , matroides bicirculares y gammoides a partir de grafos, matroides lineales a partir de matrices , etc. Sin embargo, un algoritmo para realizar cálculos en matroides arbitrarios necesita un método uniforme para acceder a su argumento, en lugar de tener que rediseñarlo para cada una de estas clases de matroides. El modelo de oráculo proporciona una forma práctica de codificar y clasificar los tipos de acceso que un algoritmo podría necesitar.

Comenzando con Rado (1942) , "funciones de independencia" o "${\displaystyle I}$Las funciones "-" se han estudiado como una de las muchas formas equivalentes de axiomatizar matroides. Una función de independencia asigna un conjunto de elementos de matroide al número${\displaystyle 1}$si el conjunto es independiente o${\displaystyle 0}$si es dependiente; es decir, es la función indicadora de la familia de conjuntos independientes, esencialmente lo mismo que un oráculo de independencia. ^{[ 7 ]}

Los oráculos matroidales también han formado parte de los primeros trabajos algorítmicos sobre matroides. Así, Edmonds (1965) , al estudiar problemas de partición de matroides, asumió que el acceso al matroide dado se realizaba a través de una subrutina que toma como entrada un conjunto independiente.${\displaystyle I}$y un elemento${\displaystyle x}$y devuelve un circuito en${\displaystyle I\cup \{x\}}$(necesariamente único y que contiene${\displaystyle x}$, si existe) o determina que no existe tal circuito. Edmonds (1971) utilizó una subrutina que prueba si un conjunto dado es independiente (es decir, en terminología más moderna, un oráculo de independencia ) y observó que la información que proporciona es suficiente para encontrar la base de peso mínimo en tiempo polinomial.

A partir del trabajo de Korte y Hausmann (1978) y Hausmann y Korte (1978) , los investigadores comenzaron a estudiar los oráculos desde el punto de vista de demostrar cotas inferiores en algoritmos para matroides y estructuras relacionadas. Estos dos artículos de Hausmann y Korte trataban el problema de encontrar un conjunto independiente de cardinalidad máxima, lo cual es fácil para matroides pero (como demostraron) más difícil de aproximar o calcular con exactitud para sistemas de independencia más generales representados por un oráculo de independencia. Este trabajo impulsó una serie de artículos a finales de la década de 1970 y principios de la de 1980 que mostraban resultados de dificultad similares para problemas en matroides ^{[ 8 ]} y comparaban la potencia de diferentes tipos de oráculos de matroides. ^{[ 9 ]}

Desde entonces, el oráculo de independencia se ha convertido en el estándar para la mayoría de las investigaciones sobre algoritmos de matroides. ^{[ 10 ]} También se ha continuado investigando sobre cotas inferiores, ^{[ 11 ]} y comparaciones de diferentes tipos de oráculos. ^{[ 12 ]}

Se han considerado los siguientes tipos de oráculos matroides.

• Un oráculo de independencia toma como entrada un conjunto de elementos de matroide y devuelve como salida un valor booleano , verdadero si el conjunto dado es independiente y falso en caso contrario. ^{[ 13 ]} Puede implementarse fácilmente basándose en la estructura subyacente a partir de la cual se definió el matroide para matroides gráficos , matroides transversales , gammoides y matroides lineales, y para matroides formados a partir de estos mediante operaciones estándar como sumas directas. ^{[ 3 ]}
• Un oráculo base toma como entrada un conjunto de elementos matroidales y devuelve como salida un valor booleano: verdadero si el conjunto dado es una base y falso en caso contrario. ^{[ 9 ]}
• Un oráculo de circuitos toma como entrada un conjunto de elementos matroidales y devuelve como salida un valor booleano: verdadero si el conjunto dado es un circuito y falso en caso contrario. ^{[ 9 ]}
• El oráculo de búsqueda de circuitos de Edmonds (1965) toma como entrada un conjunto independiente y un elemento adicional, y determina si su unión es independiente o encuentra un circuito en la unión y lo devuelve.
• Un oráculo de rango toma como entrada un conjunto de elementos de matroide y devuelve como salida un valor numérico, el rango del conjunto dado. ^{[ 9 ]}
• Se han considerado tres tipos de oráculos de cierre : uno que comprueba si un elemento dado pertenece al cierre de un conjunto dado, un segundo que devuelve el cierre del conjunto y un tercero que comprueba si un conjunto dado es cerrado. ^{[ 9 ]}
• Un oráculo de expansión toma como entrada un conjunto de elementos de matroide y devuelve como salida un valor booleano: verdadero si el conjunto dado es de expansión (es decir, contiene una base y tiene el mismo rango que todo el matroide) y falso en caso contrario. ^{[ 14 ]}
• Un oráculo de circunferencia toma como entrada un conjunto de elementos matroides y devuelve como salida un valor numérico, el tamaño del circuito más pequeño dentro de ese conjunto (o${\displaystyle +\infty }$si el conjunto dado es independiente). ^{[ 14 ]}
• Un oráculo de puerto para un elemento fijo${\displaystyle x}$del matroid toma como entrada un conjunto de elementos matroid y devuelve como salida un valor booleano, verdadero si el conjunto dado contiene un circuito que incluye${\displaystyle x}$y falso en caso contrario. ^{[ 15 ]}

Aunque existen muchos tipos conocidos de oráculos, la elección de cuál usar se puede simplificar, ya que muchos de ellos son equivalentes en potencia computacional. Un oráculo${\displaystyle X}$Se dice que es polinómicamente reducible a otro oráculo.${\displaystyle Y}$si alguna llamada a${\displaystyle X}$puede ser simulado por un algoritmo que accede al matroide usando solo oráculo${\displaystyle Y}$y toma tiempo polinomial medido en términos del número de elementos del matroide; en términos de teoría de la complejidad, esto es una reducción de Turing . Se dice que dos oráculos son polinomialmente equivalentes si son polinomialmente reducibles entre sí. Si${\displaystyle X}$y${\displaystyle Y}$son polinomialmente equivalentes, entonces cada resultado que demuestre la existencia o no existencia de un algoritmo de tiempo polinomial para un problema de matroides usando oráculo${\displaystyle X}$Esto también demuestra lo mismo para Oracle.${\displaystyle Y}$.

Por ejemplo, el oráculo de independencia es polinomialmente equivalente al oráculo de búsqueda de circuitos de Edmonds (1965) . Si se dispone de un oráculo de búsqueda de circuitos, se puede comprobar la independencia de un conjunto utilizando como máximo${\displaystyle n}$Las llamadas al oráculo comienzan con un conjunto vacío , agregan elementos del conjunto dado uno por uno y utilizan el oráculo de búsqueda de circuitos para comprobar si cada adición preserva la independencia del conjunto que se ha construido hasta el momento. En la otra dirección, si se dispone de un oráculo de independencia, el circuito en un conjunto${\displaystyle I\cup \{x\}}$puede encontrarse utilizando como máximo${\displaystyle n}$llamadas al oráculo mediante pruebas, para cada elemento${\displaystyle y\in I}$, si${\displaystyle I\setminus \{y\}\cup \{x\}}$es independiente y devuelve los elementos para los que la respuesta es no. El oráculo de independencia también es polinómicamente equivalente al oráculo de rango, al oráculo de expansión, a los dos primeros tipos de oráculo de cierre y al oráculo de puerto. ^{[ 1 ]}

El oráculo base, el oráculo de circuito y el oráculo que comprueba si un conjunto dado es cerrado son todos más débiles que el oráculo de independencia: pueden ser simulados en tiempo polinomial por un algoritmo que accede al matroide usando un oráculo de independencia, pero no a la inversa. Además, ninguno de estos tres oráculos puede simularse entre sí en tiempo polinomial. El oráculo circunferencial es más fuerte que el oráculo de independencia, en el mismo sentido. ^{[ 9 ]}

Además de las reducciones de Turing en tiempo polinomial, también se han considerado otros tipos de reducibilidad. En particular, Karp, Upfal y Wigderson (1988) demostraron que, en algoritmos paralelos , los oráculos de rango e independencia difieren significativamente en potencia computacional. El oráculo de rango permite la construcción de una base de peso mínimo mediante${\displaystyle n}$consultas simultáneas, de los prefijos del orden ordenado de los elementos del matroide: un elemento pertenece a la base óptima si y solo si el rango de su prefijo difiere del rango del prefijo anterior. En contraste, encontrar una base mínima con un oráculo de independencia es mucho más lento: se puede resolver de forma determinista en${\displaystyle O({\sqrt {n}})}$pasos de tiempo, y hay un límite inferior de${\displaystyle \Omega ((n/\log n)^{1/3})}$incluso para algoritmos paralelos aleatorios.

Se sabe que muchos problemas sobre matroides se pueden resolver en tiempo polinomial mediante algoritmos que acceden al matroide únicamente a través de un oráculo de independencia u otro oráculo de potencia equivalente, sin necesidad de ninguna suposición adicional sobre el tipo de matroide que se les ha proporcionado. Estos problemas resolubles en tiempo polinomial incluyen:

• Encontrar una base de peso mínimo o máximo de un matroide ponderado , utilizando un algoritmo voraz . ^{[ 2 ]}
• Particionar los elementos de un matroide en un número mínimo de conjuntos independientes y encontrar el conjunto más grande que sea simultáneamente independiente en dos matroides dados. Este último problema se denomina intersección de matroides , y las soluciones a ambos problemas están estrechamente relacionadas entre sí. ^{[ 16 ]}
• Probar si un matroide es${\displaystyle k}$-conectado (en el sentido de Tutte 1966 ) para${\displaystyle k\leq 3}$. ^{[ 17 ]}
• Prueba para determinar si un matroide dado es gráfico ^{[ 18 ]} o regular . ^{[ 19 ]}
• Encontrar una descomposición en orejas de un matroide dado, una secuencia de circuitos cuya unión es el matroide y en la que cada circuito permanece como tal después de que todos los circuitos anteriores de la secuencia se contraen. Dicha descomposición también puede encontrarse con la propiedad adicional de que un elemento del matroide elegido pertenece a cada circuito. ^{[ 15 ]}
• Hallar una descomposición en ramas de un matroide dado, siempre que el ancho de sus ramas no sea mayor que una constante fija. ^{[ 20 ]}
• Enumerar todas las bases, planos o circuitos de un matroide, en tiempo polinomial por conjunto de salida. ^{[ 21 ]}
• Aproximación del número de bases mediante un esquema de aproximación aleatoria de tiempo totalmente polinomial , para un matroide con${\displaystyle n}$elementos y rango${\displaystyle r}$, con la suposición adicional de que el número de bases está dentro de un factor polinomial del número de${\displaystyle r}$-conjuntos de elementos. ^{[ 22 ]}

Para muchos problemas de matroides, es posible demostrar que un oráculo de independencia no proporciona suficiente poder para permitir que el problema se resuelva en tiempo polinomial. La idea principal de estas demostraciones es encontrar dos matroides.${\displaystyle M}$y${\displaystyle M'}$en las que difiere la respuesta al problema y que son difíciles de distinguir para un algoritmo. En particular, si${\displaystyle M}$tiene un alto grado de simetría y se diferencia de${\displaystyle M'}$solo en las respuestas a un pequeño número de consultas, entonces puede requerir un número muy grande de consultas para que un algoritmo esté seguro de distinguir una entrada de tipo${\displaystyle M}$a partir de una entrada formada mediante el uso de una de las simetrías de${\displaystyle M}$permutar${\displaystyle M'}$. ^{[ 3 ]}

Un ejemplo sencillo de este enfoque puede utilizarse para demostrar que es difícil comprobar si un matroide es uniforme . Para simplificar la exposición, sea${\displaystyle n}$ser par, dejar${\displaystyle M}$ser el matroide uniforme${\displaystyle U{}_{n}^{n/2}}$y dejar${\displaystyle M'}$ser un matroide formado a partir de${\displaystyle M}$haciendo uno solo de los${\displaystyle n/2}$conjuntos base de elementos de${\displaystyle M}$dependiente en lugar de independiente. Para que un algoritmo pueda comprobar correctamente si su entrada es uniforme, debe ser capaz de distinguir${\displaystyle M}$de cada permutación posible de${\displaystyle M'}$. Pero para que un algoritmo determinista pueda hacerlo, debe probar cada uno de los${\displaystyle n/2}$-subconjuntos de elementos de los elementos: si faltara un conjunto, podría ser engañado por un oráculo que eligiera ese mismo conjunto como el que debe hacerse dependiente. Por lo tanto, probar si un matroide es uniforme puede requerir

${\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}$

consultas de independencia, mucho mayores que las polinómicas. Incluso un algoritmo aleatorio debe realizar casi tantas consultas para poder distinguir con seguridad estos dos matroides. ^{[ 23 ]}

Jensen y Korte (1982) formalizan este enfoque demostrando que, siempre que existan dos matroides${\displaystyle M}$y${\displaystyle M'}$En el mismo conjunto de elementos pero con diferentes respuestas al problema, un algoritmo que resuelve correctamente el problema dado en esos elementos debe usar al menos

${\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}$

consultas, donde${\displaystyle \operatorname {aut} (M)}$denota el grupo de automorfismos de${\displaystyle M}$,${\displaystyle Q_{i}}$denota la familia de conjuntos cuya independencia difiere de${\displaystyle M}$a${\displaystyle M'}$, y${\displaystyle \operatorname {fix} (M,Q_{i})}$denota el subgrupo de automorfismos que mapea${\displaystyle Q_{i}}$a sí mismo. Por ejemplo, el grupo de automorfismos del matroide uniforme es simplemente el grupo simétrico , con tamaño${\displaystyle n!}$y en el problema de probar matroides uniformes solo había un conjunto${\displaystyle Q_{i}}$con${\displaystyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}$, menor por un factor exponencial que${\displaystyle n!}$. ^{[ 24 ]}

Entre los problemas que se ha demostrado que son imposibles de calcular en tiempo polinomial para un algoritmo de oráculo matroide se incluyen:

• Comprobar si un matroide dado es uniforme. ^{[ 23 ]}
• Comprobar si un matroide dado contiene un matroide fijo.${\displaystyle H}$como menor de edad, excepto en los casos especiales que${\displaystyle H}$es uniforme con rango o corango como máximo uno. Más generalmente, si${\displaystyle {\mathcal {H}}}$es un conjunto finito fijo de matroides, y no hay ningún matroide uniforme en${\displaystyle {\mathcal {H}}}$, entonces no es posible probar en tiempo polinomial si un matroide dado contiene uno o más de los matroides en${\displaystyle {\mathcal {H}}}$como menor de edad. ^{[ 25 ]}
• Comprobar si un matroide dado es binario , es representable sobre algún campo fijo particular , o si existe un campo sobre el cual sea representable. ^{[ 26 ]}
• Resolver el problema de emparejamiento de matroides, en el que la entrada es un grafo y un matroide en sus vértices, y el objetivo es encontrar un emparejamiento en el grafo que sea lo más grande posible, sujeto a la restricción de que los vértices emparejados formen un conjunto independiente. ^{[ 27 ]}
• Probar si un matroide dado es autodual , transversal , bipartito , euleriano u orientable . ^{[ 3 ]}
• Calcular la circunferencia (tamaño del circuito más pequeño), el tamaño del circuito más grande, el número de circuitos, el número de bases, el número de planos, el número de planos de rango máximo, el tamaño del plano más grande, el polinomio de Tutte o la conectividad de un matroide dado. ^{[ 3 ]}

Entre el conjunto de todas las propiedades de${\displaystyle n}$Matroides de -elementos, la fracción de las propiedades que no requieren tiempo exponencial para ser probadas tiende a cero, en el límite, como${\displaystyle n}$va hasta el infinito. ^{[ 6 ]}

• Grupo de caja negra , un modelo tipo oráculo para la teoría de grupos.
• Grafo implícito , un modelo tipo oráculo para algoritmos de grafos.