Skip to main content
4 of 5
ACC0 is meant, not AC0
András Salamon
  • 2.4k
  • 2
  • 18
  • 33

$ACC^0[6] vs. NP$

In other words, it is open whether $SAT$ has polynomial size constant depth circuits using gates $\land$, $\lor$, $\lnot$, $mod_6$.

I think it is more than obvious, it is kind of embarrassing that we can't prove they are not equal. Note that we know $ACC^0[p]$ cannot compute $mod_q$ for $p\neq q \in Primes$. I think the fact that we can't prove a similar result for $mod_6$ is just lack of tools, the tools we have break as soon as we have two $mod$ gates.

Edit

Note that the barrier results does not seem to apply here.

Uniformity condition: language of direct connection graphs is in $DLogTime$.

Kaveh
  • 5.5k
  • 2
  • 37
  • 52