Почему теорема Шефера не доказывает, что P = NP?

Это, наверное, глупый вопрос, но я просто не понимаю. В другом вопросе они придумали теорему Шефера о дихотомии . Мне кажется, это доказывает, что каждая проблема CSP либо в P, либо в NP-полной, но не между ними. Поскольку каждая проблема NP может быть преобразована за полиномиальное время в CSP (потому что CSP является NP-полной), почему это не доказывает, что между P и NP-Complete нет места и, таким образом, P = NP?

Например, мои мысли звучат так: целочисленная факторизация может быть переписана как проблема выполнимости, поэтому, используя теорему Шефера, она должна быть либо в P, либо в NP-полной, но не между ними (даже если мы не можем выяснить, какая она есть).

Другой способ взглянуть на весь вопрос: почему мы не можем использовать теорему Шефера, чтобы решить, является ли целочисленная факторизация в P или в NP-полной?

РЕДАКТИРОВАТЬ: в ответ на ответ Дэвида Ричерби (это слишком долго для комментария):

Интересно, но я еще не до конца понимаю. При определении набора отношений гамма при использовании теоремы Шефера мы можем наложить на нее ограничения. Например, мы можем ограничить гамму использованием только отношений арности 2 (тогда проблема в P). Какие ограничения мы можем наложить на гамму?

Почему мы не можем наложить такие ограничения, чтобы все экземпляры CSP (гамма) были точно такими же, как (изоморфны?) L? Например, при передаче факторизации целочисленных значений для неравномерных чисел один из двух делителей двоично представлен в виде xn .. x3 x2 1. Теперь я хочу, чтобы это число было больше 1. Итак, у меня есть отношение (xn или .. или х3 или х2). Итак, я говорю, что гамма может иметь или-отношение arity n-1. Но я не хочу, чтобы это или отношение использовалось для включения других экземпляров, кроме L, в язык, поэтому я также навязываю, что x2..xn в отношении или не может иметь отрицание. Конечно, мне также нужно наложить ограничение на использование только определенных переменных.

Разве нельзя таким образом позволить CSP (гамма) быть изоморфным целочисленной факторизации? Главный вопрос: какие ограничения мы можем наложить на гамму?

РЕДАКТИРОВАТЬ 2: в ответ на ответ Ювала Filmus.

Я понимаю ваш ответ, и он кажется правильным, хотя и примерно таким же, как и ответ Дэвида. Например, мы можем уменьшить факторизацию до 3-х сат, а затем сделать вывод, что факторизация является NP-завершенной, что неправильно, потому что у 3-сат есть другие случаи, которые, вероятно, не являются факторизацией

Часть, которую я не понимаю, это когда (не) произвольный экземпляр. Например, 2-SAT также кажется мне не произвольным, потому что разрешены только клочки арности 2 (хотя я должен признать, что доказательство в таком случае все еще имеет место, поскольку оно является верхней границей, а в этом случае верхней границей является P).

Возможно, лучшим примером является NP-полнота: вопрос, связанный выше. Один из ответов дает полное доказательство Шефера. Но я налагаю нетривиальные ограничения на ввод (допустимы 2-SAT-предложения и xor-предложения, но не более того). Конечно, доказательство все еще имеет место, потому что проблемы CSP, рассмотренные в доказательстве, точно такие же, как и исходная.

Часть, которую я не понимаю, - почему мы не можем сделать подобное для факторизации? Конечно, бесполезно уменьшать его до 3-SAT, но позвольте мне дать экземпляр CSP, который разлагает число и разлагает только число (на 4 бита). (переходите к END-OF-SKIP, если вы считаете, что это возможно).

Факторизация экземпляра.

ВХОД:

$n_4n_3n_2n_1$
$m_4m_3m_2m_1$

Теперь давайте преобразуем это в экземпляр CSP

$n_5..n_1$$m_5..m_1$

$d_4d_3d_2d_1$
$e_4e_3e_2e_1$

связи:

$e_4 \lor e_3 \lor e_2$

$(d_4 \land \neg m_4) \lor (d_4=m_4 \land d_3 \land \neg m_3) \lor (d_4=m_4 \land d_3=m_3 \land d_2 \land \neg m_2) \lor (d_4=m_4 \land d_3=m_3 \land d_2=m_2 \land d_1 \land \neg m_1)$

$d_1 \land e_1 = n_1$
$(d_1 \land e_2) \oplus (d_2 \land e_1) = n_2$
$n_3 = ... ; n_4 = ...$

END-OF-ПРОПУСК

Суть в том, что при применении теоремы Шефера мы должны рассматривать только такие CSP . (Так же, как и для 2-SAT, мы рассматриваем только CSP с arity 2). При этом либо один из шести полиморфизмов верен, либо нет (за исключением некоторых причуд в теории множеств). В любом случае факторизация не является NP-промежуточным звеном.

Это также может быть сделано для 3-SAT. Затем мы должны рассматривать только (используя сокращение) экземпляры 3-SAT, которые представляют экземпляры факторизации (что больше не является 3-SAT).

Где я могу пойти не так?

$L$$\Gamma$$\Gamma$$L$$L$$\Gamma$$L$$\Gamma$

$\Gamma$$\mathrm{CSP}(\Gamma)$

$\Gamma$$\mathrm{CSP}(\Gamma)$