¿Cómo se pueden encontrar las esquinas d+1d+1d+1 del cubo unitario en RdRd\mathbb{R}^d más cercano a un punto xxx en el cubo? Utilice la métrica L1, de modo que en 4d | xxx - 0000 | = ∑xi∑xi\sum {x_i} , | xxx - 0001 | = x3+x2+x1+(1−x0)x3+x2+x1+(1−x0)x_3 + x_2 + x_1 + (1 - x_0) ( x0x0x_0 a la...
Encontré un artículo titulado " Factorizando enteros y calculando logaritmos discretos mediante aproximación diofantina " por CP Schnorr de 1993. Parece un método probabilístico con tiempo de ejecución polinomial esperado (y espacio) para realizar la factorización de enteros. Del documento: "Un...
El número c-cromático se define en el papel Particiones de gráficos en cografías . Pide el número mínimo de colores utilizados para colorear los vértices, de modo que cada clase de color sea un cograma . Cograph es un gráfico libre de P4 , es decir, no hay una ruta inducida de longitud 3. El...
Tratar de encontrar la solución óptima para WEIGHTED-MAX-3SAT, la versión ponderada del problema de optimización 3-SAT, es NP-hard. De hecho, incluso aproximar la versión no ponderada de MAX-SAT arbitrariamente es probablemente NP-duro por el teorema de PCP. Un algoritmo canónico para aproximar...
La pregunta es: ¿Existe siempre un esquema de aproximación de polivinilos para problemas con NP completo que tienen algoritmos de tiempo pseudopolinomiales (como la mochila, por
Esto está motivado por mi pregunta anterior, Algoritmos de aproximación de tiempo súper polinomial para MAX-3SAT . Para muchos problemas de optimización, para cada uno tenemos una aproximación inferior de aproximación inferior asumiendo alguna conjetura teórica de complejidad ampliamente creída. En...