Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

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

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

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

  • zdd

    Вот эти вот. ZDD в своём построении требуют условия уникальности: если мы создаём узел с переменной i и двумя подузлами (ссылками) A и B, то ссылка…

  • HashMap.

    Критику HashMap можно найти в описании crit-bit trees: http://cr.yp.to/critbit.html Сами crit-bit trees это разновидность Patricia Tree with skips.…

  • Довольно неправильное мнение об одной устаревшей статье.

    Вот тут. ARIES на самом деле сборник рецептов "как построить хранилище БД" для состояния дел до 1992 года. После 1992 года тоже кое-что придумали.…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments