Cтраница 4
Легко видеть, что m - сводимость использует возможности оракула довольно ограниченным образом: во-первых, оракулу задается только один вопрос, во-вторых, ответ на этот вопрос и считается ответом на исходный вопрос о принадлежности числа х множеству А. [46]
В заключение заметим, что полиномиально ограниченная сводимость может рассматриваться как группа вычислимой симметрии клас-са-моделей алгоритмов. VJP, Проблема Q принадлежит классу с башенной временной оценкой являются инвариантными. Возможно в будущем удастся построить теорию Галуа для сложности алгоритмов. [47]
В качестве примера того, что сводимость уграфа G упрощает решение задач анализа G, рассмотрим задачу ( см. также теорему 17) нахождения минимального ( по числу вершин) множества, содержащего по крайней мере по одной вершине из каждой зоны уграфа. Известно, что эта задача является Л - полной. [48]