Я утверждаю, что для «естественного логического CSP», если k- ограниченная версия находится в P для каждого k , то неограниченная версия также находится в P. Я определю «естественный Boolean CSP» ниже.
Теорема Шефера гласит, что булева CSP на конечном множестве отношений S находится в P, если выполнено хотя бы одно из следующих условий, и является NP-полным, если не выполняется ни одно из них:
- Каждое отношение в S (кроме константы 0) выполняется путем присвоения 1 всем его переменным.
- Каждое отношение в S (кроме константы 0) выполняется путем присвоения 0 всем его переменным.
- Каждое отношение в S эквивалентно формуле 2-CNF.
- Каждое отношение в S эквивалентно формуле Хорна-Клозе.
- Каждое отношение в S эквивалентно формуле двойного Хорна-предложения. («Формула двойного рога-клаузулы» означает формулу CNF, где каждое предложение содержит не более одного положительного литерала.)
- Каждое отношение в S эквивалентно соединению аффинных предложений.
Теперь предположим, что P ≠ NP, и рассмотрим случай, когда S бесконечно. Если k- ограниченная версия находится в P для каждого k , то по теореме Шефера каждое конечное подмножество S удовлетворяет хотя бы одному из шести указанных выше условий, а это означает, что все множество S удовлетворяет хотя бы одному из шести условий. Означает ли это, что этот CSP без ограничения арности также находится в P? Еще нет.
Когда S бесконечно, мы должны указать, как задано каждое предложение во входной формуле. Мы предполагаем , что существует некоторое сюръективное отображение из {0,1} * на S , который определяет кодировку отношений в S . Логический CSP указывается с помощью функции S и этой функции кодирования.
Обратите внимание, что в каждом из случаев 3, 4, 5 и 6, описанных выше, существует естественный способ представления отношений, удовлетворяющих условию: формула 2-CNF в случае 3, формула Хорна-условия в случае 4 и так далее. Даже если отношение эквивалентно (скажем) формуле 2-CNF, нет априорной гарантии, что его кодирование обеспечивает легкий доступ к формуле 2-CNF, которая эквивалентна ей.
Теперь мы говорим, что логический CSP естественен, когда его функция кодирования удовлетворяет следующему:
- Учитывая кодировку отношения и присваивание всем его переменным, можно ли вычислить отношение или нет за полиномиальное время. (Примечание: это гарантирует, что рассматриваемый CSP всегда находится в NP.)
- С учетом кодирования отношения, удовлетворяющего условию 3, 4, 5 или 6, его естественное представление, как указано выше, может быть вычислено за полиномиальное время.
Тогда легко увидеть, что если S удовлетворяет одному из шести вышеупомянутых условий, а кодирование для S удовлетворяет этому условию «естественности», то мы можем применить соответствующий алгоритм. Утверждение, которое я изложил в начале, можно доказать, рассматривая как случай P = NP, так и случай P ≠ NP.