Как реализовать алгоритм SCC Тарьяна для решения 2-SAT после сокращения SAT → 2-SAT? ⇐ Python

[Anonymous]

Туомас Лаакконен написал код для CSTheory StackExchange на основе своей статьи (arxiv:2304.02524, позже опубликованной в журнале). Его первоначальной целью было сокращение от SAT до Monotonic 2-SAT, но, внимательно взглянув на его код, я понял, что он на самом деле реализует сокращение от SAT до 2-SAT.
Я заметил, что 2-SAT разрешимо за полиномиальное время с использованием алгоритма Тарьяна, тогда как SAT является NP-полным — поэтому, если это сокращение корректно и полиномиально, оно подразумевает P = NP.
Сведение никогда не получается, но я не уверен, как правильно подключить решатель Tarjan.
Мне нужна помощь в программировании, чтобы создать конвейер, который:

• принимает файл .cnf или .cnf.xz в качестве входных данных
• анализирует его (формат DIMACS)
• Применяет SAT Лаакконена → сокращение 2-SAT
• Решает полученный экземпляр 2-SAT с использованием алгоритма SCC Тарьяна
• Сопоставляет решение 2-SAT обратно с назначением исходной формулы SAT
• Выводит результат в виде Файл .txt в стандартном формате решения DIMACS

Вот код сокращения SAT → 2-SAT Лаакконена:
def sat_to_2sat(n, clauses):
fresh = n + 1
nclauses = []
for clause in clauses:
if len(clause) == 2:
nclauses.append(clause)
continue
v = fresh
fresh += 1
for lit in clause:
nclauses.append((-lit, -v))
for _ in range(n):
nclauses.append((v, -fresh))
fresh += 1
return fresh - 1, nclauses