July 17th, 2021

with Cat The Cat

Про конфликты, продолжение.

Я был неправ в указании источника NP-полноты проблемы получения наименьшего конфликта.

Моё текущее понимание таково: если мы удаляем литерал l из некоторого набора путей {P}l{S}, то нам надо добавить пути {P}⨯{S} - все пути до литерала l должны вести во все пути после. Собственно, это всё то же правило разрешения, только вылезшее в другом месте.