  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.
