Instruction sequence based non-uniform complexity classes

DOI10.7561/SACS.2014.1.47zbMATH Open1424.68036MaRDI QIDQ4621176FDOQ4621176

Authors J. A. Bergstra, C. A. Middelburg 

Publication date 8 February 2019

Published in Scientific Annals of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.3297

zbMATH Keywords

single-pass instruction sequencenon-uniform complexity classprojective Boolean function family

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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.

Recommendations

• Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
• scientific article; zbMATH DE number 4090801
• Some consequences of non-uniform conditions on uniform classes
• Uniform characterizations of non-uniform complexity measures
• Nonuniform complexity classes specified by lower and upper bounds

Cited in

(5)

• Uniform characterizations of non-uniform complexity measures
• A topological approach to non-uniform complexity
• On the complexity of nonuniform wavelength-based machine
• On the complexity of the correctness problem for non-zeroness test instruction sequences
• scientific article; zbMATH DE number 4090801 (Why is no real title available?)

This page was built for publication: Instruction sequence based non-uniform complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621176)