Проблемы реализации в задаче 2-выполнимости

Question

Я хочу реализовать задачу 2-SAT для 100000 литералов.Таким образом, будет 200000 вершин.Итак, я застрял в наличии массива всех достижимых вершин из каждой вершины, пространственная сложность O(200000^2) что невозможно. Поэтому, пожалуйста, предложите решение этой проблемы.И, пожалуйста, пролейте свет на эффективную реализацию проблемы 2-SAT.

Answer 1

От Википедия:

...2-выполнимость можно решить за полиномиальное время.Как Аспвалл, Пласс и Тарьян (1979) Как замечено, экземпляр 2-выполнимости разрешим тогда и только тогда, когда каждая переменная экземпляра принадлежит другому сильно связному компоненту графа импликации, чем отрицание той же переменной.Поскольку сильно связанные компоненты могут быть найдены за линейное время с помощью алгоритма, основанного на поиске в глубину, та же граница линейного времени применима и к 2-выполнимости.

Я не буду притворяться, что понимаю большую часть этого абзаца, но, похоже, здесь является алгоритм, который можно использовать для решения проблемы 2-SAT, и он описан в этом ссылочном документе (Алгоритм линейного времени для проверки истинности некоторых количественных логических формул.).Очевидно, его можно купить в Интернете примерно за 20 долларов США.Я не уверен, полезно это или нет, но вот оно!

обновлять: Бесплатный PDF-файл того же документа можно найти здесь.Кредит идет на Лиори за находку.

Answer 2

Вся эта тема немного запутана.Да, можно решить 2-сат за линейное время, но нет - вы не можете решить ее для такого количества переменных.Время решения 2-sat линейно зависит от количества импликаций, которое для 200 000 переменных может достигать (200000*199999)/2, и, кроме того, если вы используете это решение, вам понадобится примерно такой же объем памяти. .Есть другое решение (не использовать сильно связанные компоненты, которое работает медленнее, но не требует такого большого количества памяти).