Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 17: | Строка 17: | ||
При рассмотрении параметризованной сложности значение k называется ''параметром'', который | При рассмотрении параметризованной сложности значение k называется ''параметром'', который отражает некоторую структуру входных данных или другой аспект цели вычисления. Например, k может обозначать количество ребер, которые необходимо удалить для получения графа без циклов; количество последовательностей ДНК, подлежащих выравниванию в задаче выравнивания последовательностей; максимальную глубину вложенности объявления типа у компилятора; <math>k = 1 / \epsilon \;</math> может обозначать параметризацию при анализе аппроксимации; кроме того, k также может быть составным значением, зависящим от нескольких переменных. | ||
Существуют два основных способа сравнения FPT-алгоритмов, в результате чего появилось два класса FPT-задач. В классе «f(k)» задача заключается в поиске еще более медленно растущих функций от параметра f(k), управляющих сложностью FPT-алгоритмов. Класс «кернелизации» опирается на следующую лемму, утверждающую, что задача принадлежит к разряду FPT-задач в том и только том случае, если входные данные могут быть предварительно обработаны (кернелизованы) за «обычное» полиномиальное время с получением экземпляра, размер которого ограничивается только функцией от k. | Существуют два основных способа сравнения FPT-алгоритмов, в результате чего появилось два ''класса'' FPT-задач. В классе «f(k)» задача заключается в поиске еще более медленно растущих функций от параметра f(k), управляющих сложностью FPT-алгоритмов. Класс «кернелизации» опирается на следующую лемму, утверждающую, что задача принадлежит к разряду FPT-задач в том и только том случае, если входные данные могут быть предварительно обработаны ([[кернелизация|кернелизованы]]) за «обычное» полиномиальное время с получением экземпляра, размер которого ограничивается только функцией от k. | ||
Лемма 1. Параметризованная задача <math>\Pi \;</math> является задачей с фиксированными параметрами (FPT) в том и только том случае, если существует преобразование с полиномиальным временем выполнения (относительно n и k), переводящее (x, k) в (x', k | '''Лемма 1.''' Параметризованная задача <math>\Pi \;</math> является задачей с фиксированными параметрами (FPT) в том и только том случае, если существует преобразование с полиномиальным временем выполнения (относительно n и k), переводящее (x, k) в (x', k'), такое, что: | ||
(1) (x, k) является «да-экземпляром» <math>\Pi \;</math> в том и только том случае, если (x', k') является «да-экземпляром» <math>\Pi \;</math>, | (1) (x, k) является «да-экземпляром» <math>\Pi \;</math> в том и только том случае, если (x', k') является «да-экземпляром» <math>\Pi \;</math>, | ||