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.
Gespeichert in:
| Datum: | 1998 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
1998
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/4788 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860510961361747968 |
|---|---|
| author | Bulitko, V. V. Bulitko, V. K. Булитко, В. В. Булитко, В. К. Булитко, В. В. Булитко, В. К. |
| author_facet | Bulitko, V. V. Bulitko, V. K. Булитко, В. В. Булитко, В. К. Булитко, В. В. Булитко, В. К. |
| author_sort | Bulitko, V. V. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T21:14:27Z |
| description | 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. |
| first_indexed | 2026-03-24T03:05:19Z |
| format | Article |
| fulltext |
0102
0103
0104
0105
0106
0107
|
| id | umjimathkievua-article-4788 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T03:05:19Z |
| publishDate | 1998 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/cb/7e5e0e02e2e5362e607da7d760d3a0cb.pdf |
| spelling | umjimathkievua-article-47882020-03-18T21:14:27Z On a criterion of $NP$-completeness О критерии $NP$-полноты Bulitko, V. V. Bulitko, V. K. Булитко, В. В. Булитко, В. К. Булитко, В. В. Булитко, В. К. 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. Розглядається проблема побудови критерии повних множин відносно поліноміальпо обмежених звідпостей. Запропоновані нестандартний опис множин класу $NP$, коротке доведення відомої теореми Кука та деякий критерій $NP$-повноти. Institute of Mathematics, NAS of Ukraine 1998-12-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/4788 Ukrains’kyi Matematychnyi Zhurnal; Vol. 50 No. 12 (1998); 1686–1691 Український математичний журнал; Том 50 № 12 (1998); 1686–1691 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/4788/6276 https://umj.imath.kiev.ua/index.php/umj/article/view/4788/6277 Copyright (c) 1998 Bulitko V. V.; Bulitko V. K. |
| spellingShingle | Bulitko, V. V. Bulitko, V. K. Булитко, В. В. Булитко, В. К. Булитко, В. В. Булитко, В. К. On a criterion of $NP$-completeness |
| title | On a criterion of $NP$-completeness |
| title_alt | О критерии $NP$-полноты |
| title_full | On a criterion of $NP$-completeness |
| title_fullStr | On a criterion of $NP$-completeness |
| title_full_unstemmed | On a criterion of $NP$-completeness |
| title_short | On a criterion of $NP$-completeness |
| title_sort | on a criterion of $np$-completeness |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/4788 |
| work_keys_str_mv | AT bulitkovv onacriterionofnpcompleteness AT bulitkovk onacriterionofnpcompleteness AT bulitkovv onacriterionofnpcompleteness AT bulitkovk onacriterionofnpcompleteness AT bulitkovv onacriterionofnpcompleteness AT bulitkovk onacriterionofnpcompleteness AT bulitkovv okriteriinppolnoty AT bulitkovk okriteriinppolnoty AT bulitkovv okriteriinppolnoty AT bulitkovk okriteriinppolnoty AT bulitkovv okriteriinppolnoty AT bulitkovk okriteriinppolnoty |