Investigating the Power of Circuits with $MO{D}_6$ Gates

Abstract

We consider the power of Boolean circuits with MOD${}_6$ gates. First, we introduce a few basic notions of computational complexity, and describe the standard models with which we study the complexity of problems. We then define the model of Boolean circuits, equate a restricted class of circuits with an algebraic model, and present some results from working with this algebra.

23 pages, 1 figure, unpublished undergraduate independent study work