On a criterion of $NP$-completeness
We consider the problem of construction of criteria of completeness of sets with respect to polynomially bounded reducibilities. We present a nonstandard description of sets from the class NP, a brief proof of an analog of the well-known Cook theorem, and a criterion of NP-completeness.
Saved in:
| Date: | 1998 |
|---|---|
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian English |
| Published: |
Institute of Mathematics, NAS of Ukraine
1998
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/4788 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi ZhurnalBe the first to leave a comment!