On MODkP Counting Degrees

DOI10.1002/malq.19990450305zbMath0932.03047OpenAlexW2007937931MaRDI QIDQ4264534

Juichi Shinoda, Masamitsu Ozaki

Publication date: 13 March 2000

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19990450305

zbMATH Keywords

Turing degreesnondeterministic computationpolynomial time degreespolynomial time reducibilitymany-one degrees\(\text{MOD}_k\text{P}\) degrees of recursive setscounting reducibilityembeddability of finite lattices

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28)

Cites Work

• Unnamed Item
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Relativized counting classes: Relations among thresholds, parity, and mods
• Counting classes: Thresholds, parity, mods, and fewness

This page was built for publication: On MODkP Counting Degrees