Системы метрических задач: различия между версиями

Теорема 5 [6]. Задача определения коэффициента конкурентоспособности для данного экземпляра задачи <math>MTS ((X, d_X), a_0 \in X, T) \;</math> является [[PSPACE-hard problem|PSPACE-трудной]], даже если метрика <math>d_X \;</math> является униформной. С другой стороны, если метрика dX является униформной, существует детерминированный онлайн-алгоритм с полиномиальным временем выполнения для решения задачи math>MTS((X, d_X), a_0 \in X, T) \;</math>, коэффициент конкурентоспособности которого в O(log |X|) раз превышает детерминированный коэффициент конкурентоспособности алгоритма для <math>MTS((X, d_X), a_0, T) \;</math>. Предполагается, что экземпляр <math>((X, d_X), a_0, T) \;</math> задан явным образом.