{"id":"arxiv/2606.00845","url":"https://arxiv.org/abs/2606.00845","tags":["math.LO"],"score":0,"title":"Conjunctive reducibilities and completeness","domain":"math.LO","source":"arxiv","authors":["Irakli Chitaia","Keng Meng Ng","Roland Omanadze","Andrea Sorbi"],"reviews":0,"subject":"math.LO","summary":"In this article we study the notion of completeness for conjunctive reducibilities. We investigate the relationship between $c$-completeness and $r$-completeness of computably enumerable (c.e.) sets with respect to various strong reducibilities $\\le_r$. By using simplicity properties of sets, we prove that there exist c.e. sets that are simultaneously $Q$-complete and $bd$-complete, yet fail to be $c$-complete. Similarly, there exist c.e. sets that are simultaneously $Q$-complete and $bwtt$-complete (respectively, $btt$-complete) but not $c$-complete. Furthermore, we study two restrictions…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-30","reactions":{}}