Average-Case Completeness in Tag Systems

DOI10.4230/LIPIcs.STACS.2019.20OpenAlexW2933823943MaRDI QIDQ5090467

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

bounded halting problemtag systemencoding complexityaverage-case NP-completeness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average case completeness
• Closed-form analytic maps in one and two dimensions can simulate universal Turing machines
• Small universal Turing machines
• Decision problems for semi-Thue systems with a few rules
• On the computational power of neural nets
• Undecidability and nonperiodicity for tilings of the plane
• Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
• P-completeness of Cellular Automaton Rule 110
• Average Case Complete Problems
• Matrix Transformation Is Complete for the Average Case
• Proceedings Machines, Computations and Universality 2013
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• DNA Computing
• A Cellular Automaton for Blocking Queen Games
• Formal Reductions of the General Combinatorial Decision Problem
• Membrane Computing
• Four Small Universal Turing Machines
• A survey of computational complexity results in systems and control

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