C.A.: Instruction sequences and non-uniform complexity theory

Abstract. 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 de¯ne counterparts of the complexity classes P=poly and NP=poly and formulate a counterpart of the complexity theoretic conjecture that NP 6µ P=poly. In addition, we de¯ne 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 compu-tation. We think that the theory developed opens up an additional way of investigating issues concerning non-uniform complexity