Return to Answer

$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$.

$AC^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 $AC^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$.

$AC^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 $AC^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$.

$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$.

$AC^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 $AC^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.

$AC^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 $AC^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$.