I detta papper tillämpar vi Galois teoretiska algebraiska metoder på vissa grundläggande geometriska optimeringsproblem vars igenkänningsversioner inte ens är kända för att vara i klassen NP. Framför allt visar vi att det klassiska Weberproblemet, Line - restrikted' Weber sond lem och 3-dimensionsversionen av detta problem i allmänhet inte kan lösas av radikaler över rationella områden. En: den direkta konsekvensen av dessa resultat är att det för dessa geometriska optimeringsproblem inte finns någon exakt algoritm under modeller av beräkning där roten till en algebraisk ekvation erhålls med hjälp av aritmetiska opf;rationer och extraktion av e h rötter. Detta lämnar endast numeriska eller symboliska approximationer till lösning, där komplexiteten av approximationer visas vara främst en funktion av den algebraiska graden av den optimala lösningspunkten.
Även i planet, optimala lösningar av 1-median problemet är i allmänhet inte uttryckas av radikaler över Q REF.
The Algebraic Degree of Geometric Optimization Problems
{'venue': None, 'journal': 'Discrete & Computational Geometry', 'mag_field_of_study': ['Mathematics', 'Computer Science']}