Low-Level Complexity: Logic, Automata and Circuits

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

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