Average-Case Completeness in Tag Systems

DOI10.4230/LIPICS.STACS.2019.20MaRDI QIDQ5090467zbMATH OpenOpenAlexFDO

Authors Matthew Cook, Turlough Neary

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2019.20

zbMATH Keywords

average-case NP-completenessbounded halting problemencoding complexitytag system

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Tag systems and the complexity of simple programs
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• On the theory of average case complexity
• On the Average Case Complexity of Some P-complete Problems
• Structure in average case complexity
• Average-Case Complexity
• scientific article; zbMATH DE number 5081744
• scientific article; zbMATH DE number 1008511

Cites work

• A cellular automaton for blocking queen games
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• A survey of computational complexity results in systems and control
• Average Case Complete Problems
• Average case completeness
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Decision problems for semi-Thue systems with a few rules
• DNA Computing
• Formal Reductions of the General Combinatorial Decision Problem
• Four Small Universal Turing Machines
• scientific article; zbMATH DE number 4195207 (Why is no real title available?)
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• scientific article; zbMATH DE number 3305022 (Why is no real title available?)
• Matrix Transformation Is Complete for the Average Case
• Membrane Computing
• On the computational power of neural nets
• P-completeness of Cellular Automaton Rule 110
• Proceedings of the conference on machines, computations and universality 2013, MCU 2013, Zürich, Switzerland, September 9--11, 2013
• Small universal Turing machines
• Undecidability and nonperiodicity for tilings of the plane
• Undecidability in binary tag systems and the Post correspondence problem for five pairs of words
• Universality in elementary cellular automata

This page was built for publication: Average-Case Completeness in Tag Systems

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