2008/09/02 by J.A. Bergstra, Bergstra, J. A., C.A. Middelburg +1 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #F.1.3 #FOS: Computer and information sciences #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0809.0352
openalex publication_date 2008/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop theory concerning non-uniform complexity in a setting in which the notion of single-pass instruction sequence considered in program algebra is the central notion. We define counterparts of the complexity classes P/poly and NP/poly and formulate a counterpart of the complexity theoretic conjecture that NP is not included in P/poly. In addition, we define a notion of completeness for the counterpart of NP/poly using a non-uniform reducibility relation and formulate complexity hypotheses which concern restrictions on the instruction sequences used for computation. We think that the theory developed opens up an additional way of investigating issues concerning non-uniform complexity.