|
|||||
|
|
Generic case completeness |
|
| Affiliation: | Department of Mathematics, Stevens Institute of Technology, Hoboken, NJ, USA |
| 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: | Generic-case complexity Completeness Randomized problems Bounded halting problem |
| 本文献已被 ScienceDirect 等数据库收录！ | |