Макс 2-SAT - это многочленовое время, приводимое к 2-SAT?

Question

Я знаю, что 2-SAT разрешимы в многочленом времени, а 2-SAT - это NP-Hard.

У меня есть вопрос об этом утверждении: Макс 2-SAT - это многочлена-временное приводимое до 2-SAT.Можете ли вы объяснить мне, как выглядит уменьшение?Мне нужна единственная интилина об этом, но не доказательством.

Answer 1

Я думаю, что здесь есть какая-то путаница.MAX-2-SAT - это NP-HARD (и его версия решения NP - полная), в то время как 2-SAT находится в P и, следовательно, также в NP.Это означает, что 2-SAT - это полиномиальное время, приводимое к (версия решений) MAX-2-SAT.Конверс не правда, если P= NP.

Пусть $ \ phi $ - 2-SAT формула с $ m $ clauses. Если вы действительно хотите уменьшить экземпляр $ \ phi $ 2-SAT до (версия решения) MAX-2-SAT, то это просто сумма для проверки того, будет лиПо крайней мере, $ m $ (т. Е. Все) пункты $ \ phi $ удовлетворяются.