2016/05/13 by Alexei Miasnikov, Miasnikov, Alexei, Alexander Ushakov +1
Computer Science · Mathematics · #68Q17 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #Logic in Computer Science (cs.LO) #cs.CC #cs.LO #math.GR #msc:68Q17
paper · pdf · doi:10.48550/arxiv.1606.01172
arxiv created 2016/05/13 · arxiv updated 2016/06/06
In this note we introduce a notion of a generically (strongly generically) NP-complete problem and show that the randomized bounded version of the halting problem is strongly generically NP-complete.