Локальный алгоритм принимает решение о конъюнкции K по её окрестности \(S_r(K,D)\) фиксированного порядка r в сокращённой ДНФ и по локальным пометкам соседних конъюнкций. Такой подход эффективен, когда нужное свойство действительно
Для тупиковых ДНФ есть сильные локальные результаты: принадлежность K всем тупиковым ДНФ определяется по S1, а принадлежность хотя бы одной тупиковой ДНФ — по S2. Но для участия K хотя бы в одной минимальной ДНФ фиксированного r недостаточно в общем
Что важно запомнить
- S0(K,D)={K}. Следующие окрестности строятся через пересечение множеств единиц конъюнкций.
- Ядровость и вхождение во все тупиковые ДНФ определяются по S1.
- Регулярность и вхождение хотя бы в одну тупиковую ДНФ определяются по S2.
- Для минимальных ДНФ не существует универсального локального алгоритма фиксированного индекса
Окрестность конъюнкции
Пусть D — сокращённая ДНФ и K∈D. Нулевая окрестность определяется как S0(K,D)={K}. Далее \(S_{r+1}(K,D)\) состоит из конъюнкций L∈D, для которых существует \(K'\in S_r(K,D)\) с \(N_{K'}\cap N_L\ne \varnothing\). Иными словами, порядок окрестности показывает, насколько далеко по цепочке пересекающихся максимальных граней разрешено смотреть
Что локально определяется
Теорема Квайна связывает вхождение K во все тупиковые ДНФ с ядровостью. Для проверки ядровости достаточно \(S1(K,D_f^{\text{сокр}})\). Теорема Ю. И. Журавлёва связывает отсутствие K во всех тупиковых ДНФ с регулярностью, а регулярность определяется по S2. Поэтому вопрос «входит ли K хотя бы в одну тупиковую ДНФ?» также решается по окрестности второго
Граница локального подхода
Для свойства «K входит хотя бы в одну минимальную ДНФ» ситуация принципиально иная. Сапоженко формулирует результат Журавлёва: для любого фиксированного r существуют n и функция f такие, что у каждой конъюнкции K из \(D_f^{\text{сокр}}\) можно подобрать другую функцию \(h_K\) с той же окрестностью \(S_r(K)\), но с противоположным ответом на вопрос о вхождении K в объединение минимальных
Следствие состоит в том, что локальный алгоритм фиксированного индекса r не способен решить эту задачу для всех булевых функций. Чтобы гарантировать глобальную минимальность, алгоритму в общем случае нужна информация, выходящая за любую заранее фиксированную локальную окрестность.
Пример простыми словами
Представим очень длинную цепь максимальных граней. Вокруг некоторой средней грани два экземпляра цепи могут выглядеть совершенно одинаково на расстоянии r шагов. Но далеко за пределами этой области цепи заканчиваются по-разному. Из-за этого одна и та же средняя грань может входить в минимальное покрытие в первом случае и не входить во втором. Локальный алгоритм, видящий только r шагов, различить случаи не сможет.
Частые ошибки
- Считать «локальный алгоритм» алгоритмом с малым временем работы. Здесь локальность означает ограниченность используемой окрестности, а не непосредственно вычислительную сложность.
- Переносить результаты S1 и S2 с тупиковых ДНФ на минимальные ДНФ.
- Понимать невозможность фиксированного r как запрет любых алгоритмов минимизации. Результат ограничивает именно класс локальных алгоритмов фиксированного индекса.
