TY - JOUR
T1 - Generic case completeness
AU - Miasnikov, Alexei
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2016 Elsevier Inc.
PY - 2016/12/1
Y1 - 2016/12/1
N2 - 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.
AB - 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.
KW - Bounded halting problem
KW - Completeness
KW - Generic-case complexity
KW - Randomized problems
UR - http://www.scopus.com/inward/record.url?scp=84991251190&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991251190&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2016.05.002
DO - 10.1016/j.jcss.2016.05.002
M3 - Article
AN - SCOPUS:84991251190
SN - 0022-0000
VL - 82
SP - 1268
EP - 1282
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 8
ER -