Generic case completeness
作者：
Highlights：
•
摘要
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.
论文关键词：Generic-case complexity,Completeness,Randomized problems,Bounded halting problem
论文评审过程：Received 1 September 2014, Revised 13 May 2016, Accepted 13 May 2016, Available online 7 June 2016, Version of Record 15 July 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.05.002
