The equivalence of some general combinatorial decision problems

DOI10.1090/S0002-9904-1967-11780-4zbMath0169.31201OpenAlexW2019222694MaRDI QIDQ5556434

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

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• A detailed argument for the Post-Linial theorems
• Word problems and recursively enumerable degrees at unsolvability. A first paper on Thue systems
• Recursive Unsolvability of a problem of Thue
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• The post correspondence problem
• A complex of problems proposed by Post
• Formal Reductions of the General Combinatorial Decision Problem
• Recursively enumerable sets of positive integers and their decision problems
• A variant of a recursively unsolvable problem
• The word problem

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