Instruction Sequence Based Non-uniform Complexity Classes
Jan Aldert Bergstra, Cornelis A. Middelburg · Scientific Annals of Computer Science · 2014
We present an approach to non-uniform complexity in which singlepass instruction sequences play a key part, and answer various questions that arise from this approach.We introduce several kinds of non-uniform complexity classes.One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly.Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind.We also formulate a counterpart of the well-known complexity theoretic conjecture that NP ⊆ P/poly.We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.