$ Даже сел $ $ np $ -hard?

Question

Я ищу $ NP $ Доказательство - доказательство на следующий вариант $ sat $ :

$$ Даже sat={\ langle \ phi \ rangle: \ phi \ text {имеет четное количество удовлетворяющих заданий} \} $$

Я некоторое время играю с гаджетами, но я не смог построить сокращение.Тем не менее, я чувствую, что должен быть один.Помогите!

Answer 1

$ \ textsf {evensat} $ - $ \ Oplus p $ - Комплектация (произносится как $ p $ "). Способ видеть это (i), что это дополнение $ \ textsf {oddsat} $ , который является «натуральным $ \ oplus p $ " - Комплектная проблема Точно так же $ \ textsf {SAT} $ - это «Natural $ \ mathcal {np} $ - Комплектная задача и (ii) $ \ oplus p $ закрыт под дополнением. .

Теорема Valiant-Vazirani дает рандомизированное уменьшение приготовления пищи (т. Е. Снижение многих человек) с односторонней вероятностью ошибки $ \ mathcal {o} (1 / n ) $ из $ \ textsf {SAT} $ на $ \ textsf {Evensat} $ Отказ То есть $ \ textsf {evensat} $ - $ \ mathcal {np} $ -hard под рандомизированным сокращение. Вот почему теорема Валиани-вазирани обычно говорится как $ \ mathcal {np} \ subsEtq \ mathcal {rp} ^ {\ oplus p} $ .

У нас есть $ \ mathcal {rp} ^ {\ roplus p} \ subsuteq p ^ {\ # p} $ , поэтому теорема VV значительно, чем То, что вы получите от теоремы Тоды.

Маловероятно, что $ \ textsf {Evensat} $ - $ \ mathcal {np} $ -Крессия, потому что тогда полиномальная иерархия разрушается на первом уровне, $ pH= NP $ . Это открытый вопрос, будь то $ np $ и $ \ Oplus p $ сопоставимы, пока есть только доказательства Oracle, что они не получательны. (Я не знаю, в целом, как правило, что доблестно-вазирани может быть сделано от $ \ mathcal {np} \ subsEtq \ mathcal {rp} ^ {\ oplus p} $ < / span> $ \ mathcal {np} \ sombestq \ mathcal {p} ^ {\ oplus p} $ . В этом случае, поскольку $ p ^ {\ oplus p}=oplus p $ , у нас будет $ \ mathcal {np} \ subsretq \ oplus p $ . Если я правильно прочитал [1], то это не обычно доказано, поскольку он разрушит полиномиальную иерархию)

[1] Dell, HOLGER, et al. «Вероятность выделения доблестных вазирани - улучшена?». Вычислительная сложность 22.2 (2013): 345-383.

Answer 2

.открытая проблема. Мы знаем, что $ np \ subset BPP ^ {mod_2 sat} $