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 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.

31 pages; 31 pages, improvements of several proof outlines; 33 pages, presentation of section 7 improved

References in corpus (9)

• Instruction sequences with indirect jumps
• Projection semantics for rigid loops
• Thread extraction for polyadic instruction sequences
• Interface groups and financial transfer architectures
• Program algebra with a jump-shift instruction
• On the expressiveness of single-pass instruction sequences
• Autosolvability of halting problem instances for instruction sequences
• Tuplix Calculus Specifications of Financial Transfer Networks
• Instruction sequences with dynamically instantiated instructions

Cited by in corpus (10)

• Instruction sequence based non-uniform complexity classes
• Putting Instruction Sequences into Effect
• On the expressiveness of single-pass instruction sequences
• An Instruction Sequence Semigroup with Involutive Anti-Automorphisms
• Transmission protocols for instruction streams
• Instruction sequence notations with probabilistic instructions
• A process calculus with finitary comprehended terms
• Meadow enriched ACP process algebras
• A protocol for instruction stream processing
• Instruction sequences for the production of processes