I detta dokument undersöks komplexiteten hos flera geometriska problem på grund av obegränsade dimensioner. De problem som beaktas är: i) minsta omslag av punkter per enhet kuber, ii) minsta omslag av punkter per enhet bollar, och iii) minsta antal linjer för att träffa en uppsättning bollar. Var och en av dessa problem har visat sig inte ha ett polynom approximationssystem om inte P = NP. Speci c lägre gränser för de felförhållanden som kan uppnås i polynomtid anges, förutsatt att P 6 = NP. I synnerhet, Det visas att täcka med t wo kuber är i P medan täcka med tre kuber är NP-komplett.
Euclidean p-center problemet är NP-hård REF.
On the Complexity of Some Geometric Problems in Unbounded Dimension
{'venue': 'J. Symb. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}