The equivalence of some general combinatorial decision problems

DOI10.1090/S0002-9904-1967-11780-4MaRDI QIDQ5556434zbMATH OpenOpenAlexFDO

Authors W. E. Singletary

Publication date 1967

Published in Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/s0002-9904-1967-11780-4

zbMATH Keywords

recursion theory, constructive mathematics

Cites work

• A complex of problems proposed by Post
• A detailed argument for the Post-Linial theorems
• A variant of a recursively unsolvable problem
• Formal Reductions of the General Combinatorial Decision Problem
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3595166 (Why is no real title available?)
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Recursive unsolvability of a problem of Thue
• Recursively enumerable sets of positive integers and their decision problems
• The post correspondence problem
• The word problem
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems

Cited in

(4)

• Combinatorial systems. I: Cylindrical problems
• Degrees of unsolvability associated with Markov algorithms
• Combinatorial systems defined over one- and two-letter alphabets
• The many-one equivalence of some general combinatorial decision problems

This page was built for publication: The equivalence of some general combinatorial decision problems

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