Generic case completeness

Alexei Miasnikov; Alexander Ushakov

doi:10.1016/j.jcss.2016.05.002

Generic case completeness

Department of Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Pages (from-to)	1268-1282
Number of pages	15
Journal	Journal of Computer and System Sciences
Volume	82
Issue number	8
DOIs	https://doi.org/10.1016/j.jcss.2016.05.002
State	Published - 1 Dec 2016

Keywords

Bounded halting problem
Completeness
Generic-case complexity
Randomized problems

Access to Document

10.1016/j.jcss.2016.05.002

Cite this

@article{fb46abe0584b41478d0cb02454ca55a7,

title = "Generic case completeness",

abstract = "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.",

keywords = "Bounded halting problem, Completeness, Generic-case complexity, Randomized problems",

author = "Alexei Miasnikov and Alexander Ushakov",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2016",

month = dec,

day = "1",

doi = "10.1016/j.jcss.2016.05.002",

language = "English",

volume = "82",

pages = "1268--1282",

number = "8",

}

TY - JOUR

T1 - Generic case completeness

AU - Miasnikov, Alexei

AU - Ushakov, Alexander

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 - https://www.scopus.com/pages/publications/84991251190

UR - https://www.scopus.com/pages/publications/84991251190#tab=citedBy

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 -

Generic case completeness

Abstract

Keywords

Access to Document

Other files and links

Cite this