Сложность конкретных случаев Max2Sat

Question

Я знаю, что Max2Sat является NP-Complete в целом, но мне интересно, если некоторые ограничимые случаи известны в P. Конечно, языки

$ l_k:={\ phi \, | \, \ phi \, \ text {представляет собой экземпляр 2SAT, который имеет задание, удовлетворяющее по крайней мере K Clauses.} \ } $

можно решить в $ O (n ^ k) $ через поиск грубой силы, поскольку для каждого языка $ K $ исправлено. Однако мне интересно относиться к случаю, когда указывается доля пункта. Любая фракция дает проблему неприятности NP? В частности, мне интересно относиться к случаю удовлетворения по меньшей мере половины половины пункта экземпляра 2SAT.

Уменьшение, которое я видел из 3SAT до Max2SAT, конструирует 10 пунктов из каждого пункта в 3SAT такое, что из этих десяти, ровно 7 удовлетворяются, когда исходное предложение 3SAT выполнено, и не более 6 удовлетворены, когда первоначальная статья не удовлетворена Отказ Таким образом, в этом сокращении доля 7/10 $ работает, но $ 1/2 $ не потому, что неудовлетворительная правда Назначения экземпляра 3SAT все еще могут приносить экземпляр 2SAT, который имеет задание, удовлетворяющее более половине половины пунктов. Я думал о другом строительстве или добавления дополнительных положений в экземпляр 2SAT, но я был неудачным до сих пор.

Answer 1

Вы всегда можете удовлетворить по крайней мере половину половины пунктов: для каждой переменной $ x $ , найдите количество пунктов, которые содержат $ x $ и количество пунктов, которые содержат $ \ lnot x $ . Выберите тот, который удовлетворяет большинство пунктов. Удалить пункты, содержащие $ x $ и $ \ lnot x $ . Повторите для других переменных.

Поскольку для каждого $ x $ Мы удовлетворяем по крайней мере половину удаленных пунктов, мы удовлетворяем половину пунктов в целом.

С другой стороны, также тесно: пусть $ \ alpha> \ frac 12 $ БЫЛ доля пункта, для которых мы можем дать ответ. Пусть $ \ beta> \ frac 12 $ - максимальная доля пунктов, мы можем удовлетворить в конкретном пункте. Затем мы можем добавить пункты, так что $ \ beta $ (для нового пункта) становится произвольным предложением $ \ alpha $ < / span>:

.
• Если $ \ beta <\ alpha $ , то мы можем добавить пункты $ (x_i \ lor \ lnot x_i) $ , до $ \ beta> \ alpha $ (поскольку эти пункты всегда верны, $ \ beta $ увеличивается).
• Если $ \ beta> \ alpha $ , мы можем добавить пункты $ (x_i) $ и $ (\ lnot x_i) $ , до $ \ beta <\ \ alpha $ (так как ровно половина пунктов ИСТИНА, $ \ beta $ уменьшается).

Я не проверял, но чтобы получить $ o (\ frac 1m) $ Разница (то есть, чтобы найти точное количество пунктов), я думаю, что это хватает Чтобы добавить $ O (M) $ пункты. Другими словами, если мы сможем решить для некоторых $ \ alpha> \ frac 12 $ , мы можем проверить на любой $ \ Beta $ $ \ beta $ flation of tavest могут быть удовлетворены, и поэтому мы можем решить Max2Sat в полиноме.