Preguntas etiquetadas con apx

¿APX está contenido en NP?

Se dice que un problema P está en APX si existe alguna constante c> 0 tal que existe un algoritmo de aproximación de tiempo polinómico para P con factor de aproximación 1 + c. APX contiene PTAS (visto simplemente seleccionando cualquier constante c> 0) y P. ¿APX está en NP? En particular,...

¿La dureza aproximación (para algunos ) implica dureza ?

Suponga que para un problema de minimización dado con solo soluciones enteras, es difícil decidir si la solución óptima es 5 o 6. Es decir, un algoritmo de tiempo polinomial con una relación de aproximación mejor que 6/5 implicaría .nortePAGSnortePAGSNPPAGS= NPAGSPAGS=nortePAGSP=NP 1) ¿Esto...