Asumo familiaridad con las clases de complejidad P (complejidad) y NP (complejidad). Hablando sucintamente, [matemática] P [/ matemática] consiste en todos los problemas que pueden resolverse eficientemente. [math] NP [/ math], por otro lado, consiste en todos los problemas cuya solución se puede verificar eficientemente.
[math] NP [/ math] a menudo se malinterpreta como “tiempo no polinomial”, pero la forma correcta de interpretarlo es como “tiempo polinomial no determinista”. La equivalencia entre el no determinismo y la verificación de una solución se puede mostrar fácilmente.
El clásico [math] P \ stackrel {?} {=} NP [/ math] pregunta si las dos clases son iguales, es decir, si un problema [math] NP [/ math] se puede resolver de manera eficiente.
- ¿Existe una diferencia importante entre los vectores con forma (D,) y (D, 1) o (1, D) en numpy?
- Suponiendo que uno tenga una experiencia limitada en programación, matemáticas y neurociencia, ¿cómo se ingresa a un programa de posgrado para inteligencia artificial o neurociencia computacional?
- ¡Un conjunto de idiomas de más de {0,1} que no son recursivamente enumerables son incontables! ¿Cómo puedo probarlo?
- Coloque números de cinco bits en los vértices de un hipercubo de 9 dimensiones de modo que, desde cualquier vértice, pueda alcanzar cualquier número en no más de dos movimientos a lo largo de los bordes del hipercubo.
- ¿Cuál es el mejor menor para una especialización en informática? ¿Un menor le dará una 'ventaja' en la fuerza laboral?
Este problema fue formulado por primera vez por Stephen Cook en 1971 y desde entonces ha seguido siendo la mayor pregunta abierta de la ciencia teórica de la informática. Es uno de los siete problemas del Premio del Milenio y conlleva un $ 1 millón para la primera solución correcta.
Desde su inicio, los científicos informáticos han tenido poco éxito tratando de probar o refutar la desigualdad.
Suponiendo que [math] P \ neq NP [/ math], los investigadores comenzaron a preguntar si podemos encontrar una solución casi óptima: una que no sea óptima pero que no esté muy lejos de lo óptimo.
Considere un problema de minimización de optimización [matemática] NP – [/ matemática], digamos problema de cobertura de Vértice. El problema es: dado un gráfico no dirigido [matemática] G = (V, E) [/ matemática], encuentre un subconjunto de vértices [matemática] V ^ \ prime \ subseteq V [/ matemática] de cardinalidad mínima de manera que cada borde tenga al menos un incidente de punto final en [matemática] V ^ \ prime [/ matemática]. Un subconjunto de vértices que satisfacen la propiedad anterior se denomina Cubierta de vértice (VC). Necesitamos encontrar la cubierta de vértice de mínima cardinalidad.
Vamos a la solución del problema anterior como [math] OPT [/ math]. Claramente, la cardinalidad de cualquier VC será mayor o igual que [math] OPT [/ math]. Supongamos que un algoritmo [matemático] \ matemático {A} [/ matemático] devuelve un VC que siempre es como máximo [matemático] \ alfa [/ matemático] ([matemático] \ alfa> 1 [/ matemático]) veces [matemático] OPT [/mates]. A este algoritmo lo llamamos algoritmo de aproximación del factor [math] \ alpha [/ math]. Deje que la solución devuelta por [math] \ mathcal {A} [/ math] sea [math] appx [/ math]. Tenemos
[math] OPT \ le appx \ le \ alpha \ cdot OPT [/ math].
En otras palabras,
[matemáticas] \ frac {appx} {OPT} \ le \ alpha [/ math].
Para un problema de maximización, el factor de aproximación se define de manera análoga. Tenga en cuenta que aquí, [math] \ alpha <1 [/ math].
El análisis de un algoritmo de aproximación es difícil y no hay una forma general de hacerlo. Sin embargo, el diseño del algoritmo de aproximación se puede dividir ampliamente en las siguientes categorías:
- Métodos clásicos:
- Algoritmo codicioso o búsqueda local: los algoritmos son fáciles de diseñar, pero su análisis puede ser un poco complicado. Ejemplo: Establezca un problema de cobertura que admite un factor de aproximación de [math] \ mathcal {O} (\ log {} n) [/ math].
- Programación dinámica: los ejemplos de esta categoría incluyen el problema de la mochila y el problema del embalaje del contenedor. Puede acercarse arbitrariamente a la solución pero nunca igual a la solución óptima real, es decir, [math] appx \ le (1 + \ epsilon) OPT [/ math] y el tiempo de ejecución depende de [math] \ epsilon [/ math]. Para obtener más información, consulte: Esquema de aproximación de tiempo polinómico.
- Técnicas basadas en programación convexa: en este tipo de métodos, primero escriba el programa como un programa convexo y luego intente encontrar su solución. Asumo familiaridad con la optimización convexa y la teoría de la dualidad. Si no, pase a la siguiente sección.
- Programación lineal: escriba la formulación de programación entera del problema de optimización y relájela a un programa lineal.
- Adaptación dual: la solución codiciosa se interpreta como variables duales. Reduzca las variables duales dividiéndolas por la constante apropiada de modo que se cumplan todas las restricciones duales. Esta constante resulta ser la relación de aproximación.
- Redondeo aleatorizado: tome un programa entero, relájelo a un programa lineal, resuelva el programa lineal y redondee de nuevo a un valor integral. Ejemplo: algoritmo de aproximación del factor [math] f [/ math] para Set Cover donde [math] f [/ math] es la frecuencia máxima de un elemento.
- Esquema dual primario: este algoritmo se basa en la condición de holgura complementaria primaria y la condición de flojedad complementaria dual. Comience con un valor inicial y actualice las variables primarias y las variables duales de modo que se cumplan todas las restricciones.
- Programación semidefinida: esta técnica se basa en la programación cuadrática y se basa en la teoría de la matriz semidefinida positiva. Esto fue iniciado por un artículo seminal de Michel Goemans y David Williamson, quienes aplicaron la programación semidefinida para llegar a un factor de aproximación mejorado para el problema de corte máximo.
- Proyección de hiperplano aleatorio: escriba la programación cuadrática para un problema de optimización, relájela a programa vectorial, cámbiela a un programa semidefinido introduciendo una matriz semidefinida positiva adecuada, resuélvala y redondea las soluciones proyectándolas en un hiperplano aleatorio.
- Esquema Primal Dual: Esta es una técnica relativamente nueva introducida por Arora & Kale donde utilizan el Método de actualización de pesos multiplicativos de matriz (MMW) para actualizar las variables primarias y duales (como se define en el esquema Primal Dual para LP).
