Instruction sequence based non-uniform complexity classes

Abstract

We present an approach to non-uniform complexity in which single-pass 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 is not included in P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.

33 pages, supersedes arXiv:0809.0352 [cs.CC] in many respects (see end of introduction); remarks added

References in corpus (1)

• An Instruction Sequence Semigroup with Involutive Anti-Automorphisms

Cited by in corpus (10)

• On algorithmic equivalence of instruction sequences for computing bit string functions
• On instruction sets for Boolean registers in program algebra
• Instruction sequence expressions for the secure hash algorithm SHA-256
• Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers
• Instruction sequences expressing multiplication algorithms
• On the complexity of the correctness problem for non-zeroness test instruction sequences
• Long multiplication by instruction sequences with backward jump instructions
• Program algebra for Turing-machine programs
• Axioms for behavioural congruence of single-pass instruction sequences
• Program algebra for random access machine programs