Hardness of the Binary Covering Radius Problem in Large Norms
Il documento dimostra che il problema decisionale di approssimazione del raggio di copertura sui reticoli nella norma è NP-difficile per una funzione esplicita di approssimazione quando supera circa 35.31, estendendo i risultati precedenti sulla difficoltà di problemi correlati nella norma .
Immagina di essere in una stanza piena di punti luminosi che formano un motivo geometrico perfetto, come una griglia di stelle nel cielo.…