Low-Level Complexity: Logic, Automata, and Circuits

点击翻译按钮获取中文摘要

Complexity classes originally based on uniform families of boolean circuits have been shown to have equivalent definitions using finite monoids and first-order logic. Research in this area has provided a new synthesis of descriptions of low-level complexity classes - sets of formal languages which can be recognized under tight resource bounds in various models of computation. This project will apply this synthesis to the separation of low-level complexity classes, the study of uniformity of circuit families, and the extension of the circuit model to new kinds of computation.