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.
Збережено в:
| Дата: | 1998 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
1998
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/4788 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
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 |