Instruction sequence based non-uniform complexity classes

DOI10.7561/SACS.2014.1.47zbMATH Open1424.68036arXiv1301.3297MaRDI 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)

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.

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

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

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)

Cited In (4)

• On the complexity of nonuniform wavelength-based machine
• On the complexity of the correctness problem for non-zeroness test instruction sequences
• Title not available (Why is that?)
• Uniform characterizations of non-uniform complexity measures

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)