Hardness of the Binary Covering Radius Problem in Large Norms
Este artigo demonstra que o problema de decisão de raio de cobertura aproximado em reticulados na norma é NP-difícil para uma função explícita de fator de aproximação quando , estabelecendo a primeira prova de dureza para esse problema em normas explícitas.
Imagine que você tem um mapa de uma cidade infinita, mas em vez de ruas e avenidas, o mapa é feito de pontos espalhados de forma muito organizada.…