Показано, что для реоптимизации задачи о покрытии множества при установлении или освобождении элемента в производную множенства не существует полиномиально приближенной схемы. Похожий результат имеет место для задачи "минимиального раскрашивания графа" при установлении производной вершины не более чем с двумя инцидентными ее ребрами.
