Considere los problemas de optimización de la siguiente forma. Sea una función computable en tiempo polinómico que mapea una cadena en un número racional. El problema de optimización es este: ¿cuál es el valor máximo de sobre cadenas de bits ?
Digamos que tal problema tiene una caracterización de minimax , si hay otra función computable de tiempo polinomial , tal que cumple. Aquí x corre sobre todas las cadenas de n bits, yy corre sobre todas las cadenas de m bits; n y m pueden ser diferentes, pero están polinomialmente relacionados.max x f ( x ) = min y g ( y ) x n y m n m
Numerosos problemas de optimización naturales e importantes tienen tal caracterización minimax. Algunos ejemplos (los teoremas en los que se basan las caracterizaciones se muestran entre paréntesis):
Programación lineal (LP Duality Thm), flujo máximo (Max Flow Min Cut Thm), Max Bipartite Matching (Konig-Hall Thm), Max Non-Bipartite Matching (Tutte's Thm, Tutte-Berge formula), Max Disjoint Arborescences en gráfico dirigido ( Edmond's Disjoint Branching Thm), Max Spanning Tree Packing en gráfico no dirigido (Tutte's Tree Packing Thm), Min Covering by Forests (Nash-Williams Thm), Max Directed Cut Packing (Lucchesi-Younger Thm), Max 2-Matroid Intersection (Matroid Intersection Thm), Max Disjoint Paths (Menger's Thm), Max Antichain en conjunto parcialmente ordenado (Dilworth Thm), y muchos otros.
En todos estos ejemplos, también está disponible un algoritmo de tiempo polinómico para encontrar el óptimo. Mi pregunta:
¿Hay algún problema de optimización con una caracterización minimax, para el cual no se ha encontrado un algoritmo de tiempo polinómico hasta ahora?
Nota: ¡La programación lineal estuvo en este estado durante aproximadamente 30 años!
Seymour y Thomas mostraron una caracterización mínima-máxima del ancho del árbol. Sin embargo, el ancho del árbol es NP-duro. Sin embargo, este no es el tipo de caracterización que está solicitando, porque la función dual no es una función computable de tiempo polinómico de un certificado corto. Es muy probable que esto sea inevitable para problemas completos de NP, porque de lo contrario tendríamos un problema de NP completo en coNP, lo que implica un colapso NP = coNP, y lo consideraría bastante sorprendente.g
El treewidth de un gráfico es igual a la anchura más pequeña más pequeña de una descomposición árbol de G . La descomposición de un árbol de un gráfico G es un árbol T tal que cada vértice x de T está etiquetado por un conjunto S ( x ) de vértices de G con la propiedad:G G G T x T S(x) G
Seymour y Thomas demostraron que el ancho de árbol es igual al número de zarzas de : el k máximo de tal manera que haya una colección de subgráficos conectados de G para que:G k G
Tal colección de subgrafías se llama zarza de ordenk
Observe cómo "número de zarza es al menos " es una declaración ∃ ∀ , con ambos cuantificadores sobre conjuntos exponencialmente grandes. Por lo tanto, no sugiere un certificado fácil de verificar (y si hubiera uno que sería una gran noticia, como dije anteriormente). Para hacer las cosas aún peor, Grohe y Marx mostraron que para cada k no es un gráfico de treewidth k tal que cualquier zarza de orden al menos k 1 / 2 + ε debe consistir de manera exponencial muchos subgraphs. También muestran que existen zarzas de orden k 1 / 2 / O ( log 2k ∃∀ k k k1/2+ϵ de tamaño polinómico.k1/2/O(log2k)
fuente
Los juegos de paridad, los juegos de pago medio, los juegos con descuento y los juegos estocásticos simples entran en esta categoría.
Todos ellos son infinitos juegos de suma cero de dos jugadores que se juegan en gráficos, donde los jugadores controlan los vértices y eligen a dónde debe ir una ficha. Todos tienen equilibrios en las estrategias posicionales sin memoria, lo que significa que cada jugador elige una ventaja en cada vértice de elección de manera determinista e independiente de la historia del juego. Dada una estrategia de un jugador, se puede calcular la mejor respuesta del otro jugador en tiempo polinómico, y la relación min-max que necesita se mantiene para el "valor" del juego.
Las variantes de decisión natural de estos problemas están en NP y co-NP (de hecho UP y co-UP) y los problemas de función, para encontrar un equilibrio, se encuentran en PLS y PPAD.
Ver, por ejemplo,
David S. Johnson. 2007. La columna de completitud de NP: Encontrar agujas en pajares. ACM Trans. Algoritmos 3, 2, Artículo 24 (mayo de 2007). DOI = 10.1145 / 1240233.1240247 http://doi.acm.org/10.1145/1240233.1240247
fuente