Fine-grained complexity meets IP = PSPACE
In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from an exact to an approximate solution for a host of such problems. As one (notable) example, we show that the Closest-LCS-Pair problem (Given...
| Автори: | , |
|---|---|
| Інші автори: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Society for Industrial and Applied Mathematics
2021
|
| Онлайн доступ: | https://hdl.handle.net/1721.1/129577 |