Есть ли веб-страница для тестирования моей программы 3-SAT?

Question

Я написал программу для задачи 3-SAT. Есть ли веб-страница, где я могу получить несколько тестов или загрузить программу, чтобы проверить, работает ли она?

Answer 1

Вы можете заглянуть в проект Tough SAT. Это создаст экземпляры CNF SAT, которые не обязательно будут 3-SAT, но вы можете довольно легко конвертировать в 3-SAT, используя следующее сокращение из Википедии:

(l1 or ... or ln) -> (l1 or l2 or x2) and (not x2 or l3 or x3) and ... and (not x(n-3) or l(n-2) or x(n-2)) and (not x(n-2) or l(n-1) or ln)

Мне бы очень хотелось, чтобы они поддерживали встроенный математический синтаксис в stackru. Это обычно не противоречит другим вещам, и лучше для таких вопросов. Как правило, приведенное выше сокращение добавляет новые переменные x2 через x(n-2) так что новый экземпляр 3-SAT равнозначен исходному предложению CNF SAT (т. е. при любом назначении этих переменных условия из исходного предложения будут по-прежнему применяться). l1 через ln являются литералами.