Как именно макс 2 сб сокращается до 3 сб?
Я читал эту статью, которая пытается объяснить, как проблема с max 2 sat по сути является проблемой 3 sat и сложна для NP.
Однако, если вы видите статью, я не могу понять, почему после ci выполнено 7 из 10 пунктов, а если оно не выполнено, 6 из 10 пунктов удовлетворяются.
Может ли кто-нибудь объяснить мне в простых терминах и демистифицировать то, что именно эта статья хочет передать? По сути, я узнал, что проблема max-2-sat аналогична проблеме 3-sat. Вопрос в том, что я не могу понять, почему.
Более формально я хочу решить эту проблему:
Рассмотрим проблему MAX2SAT, описанную следующим образом.
Учитывая булево выражение 2-CNF (конъюнктивная нормальная форма) (с m предложениями, n переменными) и целым числом k, определите, существует ли присваивание, удовлетворяющее по крайней мере 'k' из всех предложений? Вычислить класс сложности (P или NP или NP Complete) MAX2SAT с обоснованием.
1 ответ
Что ж, ключевое недоразумение, о котором мы должны поговорить в первую очередь, заключается в том, что это не уменьшает Max-2-sat до 3-sat, как говорится в вашем названии. Чтобы доказать, что что-то (в данном случае Max-2-sat) является np-трудным, мы должны сделать обратное и свести к нему 3-sat (или любую другую известную проблему np-hard).
Если мы сделаем это, то мы покажем, что ЕСЛИ вещь, которую мы уменьшили до (max-2-sat), не является np-hard, то THEN 3-sat не является ни тем, ни другим, потому что мы могли бы просто сделать наше сокращение и решить 3-sat эффективно через макс-2-сб. Мы знаем, что это невозможно (3-sat известен как np-complete, кто-то другой сделал тяжелую работу), поэтому идея, что max-2-sat не np-hard, является противоречием.
Снижение до 3-х сел не говорит нам много. Макс-2-сат все еще может быть легким в этом случае. В этом случае, возможно, снижение до 3-х сат было просто плохой идеей, и проще просто заняться этим напрямую. Только обратное доказывает то, что вы пытаетесь показать