I was recently at AT&T visiting for a few weeks, and I was lucky enough to catch a talk by Amit Chakrabarti on lower bounds for multi-player pointer jumping. A complexity class that figured prominently in his talk was the class ACC0, which consists of constant depth, unbounded fanin, poly sized circuits with AND, OR, NOT and MOD m gates, for all m.
Suppose we make our life simple by fixing m to be a single prime, like 3. It turns out that the corresponding class AC0[m] can be contained strictly within NC1: this arises from results in the 80s by Razborov and Smolensky. Now suppose that instead of picking a prime integer, we choose a number like 6, which is the product of distinct primes. We do not even know whether AC0[6] = NP or not !
When you say "contained within", I assume you mean "separated from".
ReplyDeleteNo I guess he means "is a strict subset of"!
ReplyDeleteYes, I mean 'is a strict subset of'. I fixed it. thanks.
ReplyDeleteHalting problem (unary input) is in AC0 so AC0[6]
ReplyDeleteis not equal to NP.
I believe the open problem
is whether NP belongs to AC0[6] or not.
Or do I ignore sth here?
"Halting problem (unary input) is in AC0"
ReplyDeleteWhy?!
If HALTING is in AC0, can't we just solve any recognizable problem in AC0 as well? But this obviously can't be true as we know that very simple things like PARITY are not in AC0!
ReplyDeleteSuresh probably meant uniform AC^0[6] for which the halting problem example doesn't work. Allender and Gore proved that the Permanent is not in uniform AC^0[6] but that doesn't rule out NP being contained in uniform AC^0[6].
ReplyDeleteIt's possible that NEXP is contained in non-uniform AC0[6].
ReplyDeleteWhat is the status of non-uniform AC0[6]?
ReplyDelete