É $ até mesmo-sat $ $ np $ -Hard?

Question

Estou à procura de uma $ NP $ - prova de adesão para a seguinte variante da $ SAT $ :

$$ Mesmo-sat={\ langle \ phi \ rangle: \ phi \ text {tem um número par de atribuições satisfatórias}} $$

Eu tenho jogado com gadgets por um tempo, mas não consegui construir uma redução.Ainda assim, sinto que deveria haver um.Ajuda!

Answer 1

$ \ textos {evenat} $ é $ \ OPLUS P $ -complete (pronunciado "paridade $ P $ "). A maneira de ver isso é (i) que é o complemento da $ \ Textsf {Oddsat} $ , que é "a" classe "natural $ \ OPLUS P $ -complete problema da mesma maneira $ \ textsf {sat} $ é" a "classe span" natural Recipiente de Matemática "> $ \ Mathcal {NP} $ - problema -Complete, e (ii) $ \ OPLUS P $ está fechado sob complemento. .

O teorema Valiant-Vazirani dá uma redução ao cozinheiro randomizado (ou seja, uma redução de muitos um) com uma probabilidade de erro unilateral de $ \ mathcal {O} (1 / N $ de $ \ textsf {sat} $ para $ \ textos {evenat} $ . Isto é, $ \ textos {evenat} $ é $ \ mathcal {np} $ -hard sob randomizado reduções. É por isso que o teorema Valiani-Vazirani é normalmente indicado como $ \ mathcal {np} \ subseteq \ mathcal {rp} ^ {\ oplus p} $ .

temos $ \ mathcal {rp} ^ {\ oplus p} \ subseteq p ^ {\ # p} $ , então o teorema de vv é um pouco mais apertado do que O que você receberia do teorema de Toda.

É improvável que $ \ textsf {evenat} $ é $ \ mathcal {np} $ -Complete, porque então a hierarquia polinômica desmorona para o primeiro nível, $ pH= NP $ . É uma pergunta aberta se $ NP $ e $ \ OPLUS P $ são comparáveis, até agora há apenas provas da Oracle de que são incomparáveis. (Eu não sei se é geralmente conjectado que Valiant-Vazirani pode ser derandomizado de $ \ mathcal {np} \ subseteq \ mathcal {rp} ^ {\ oplus p} $ < / span> para $ \ mathcal {np} \ subseteq \ mathcal {p} ^ {\ oplus p} $ . Nesse caso, desde a matemática $ p ^ {\ oplus p}=Oplus p $ , teríamos $ \ mathcal {np} \ subseteq \ oplus p $ . Se eu ler [1] corretamente, então é não geralmente conjecturado, já que colapsaria a hierarquia polinomial)

[1] Dell, Holger, et al. "A probabilidade de isolamento de Vazirani é improvávelável?" Complexidade Computacional 22.2 (2013): 345-383.

Answer 2

Sabe-se que $ np \ subcinter p ^ {\ # p} $ De acordo com o teorema de toda a Toda, mas agora a sua pergunta "np hardnes de até mesmo sáb" éum problema aberto. sabemos que $ np \ subconjunto bpp ^ {mod_2 sentado} $