由电路定义的枚举类

《ACM Transactions on Computation Theory》：Enumeration Classes Defined by Circuits

　　

摘要

我们通过引入使用布尔电路作为枚举器的非常低级别的分类方法，来细化枚举问题的复杂性框架。我们将一些众所周知的枚举问题（例如来自图论的问题、格雷码枚举以及命题可满足性问题）归类到这些级别中。通过这种方式，我们建立了一个框架，用于区分不同问题的复杂性。这些问题至今为止还没有正式的比较方法。