Зображення обкладинки

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
Автори:	Bulitko, V. V., Bulitko, V. K., Булитко, В. В., Булитко, В. К.
Формат:	Стаття
Мова:	Російська Англійська
Опубліковано:	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

Схожі ресурси

Solvability of NP-complete problems
за авторством: O. A. Vahis, та інші
Опубліковано: (2022)

NP-трудность задач оптимизации коллективного преследования
за авторством: Пашко, С.В.
Опубліковано: (2014)

NP-hardness of collective pursuiting optimization problems
за авторством: Pashko, S.V.
Опубліковано: (2025)

О классе NP и NР-полных задачах
за авторством: Листровой, С.В.
Опубліковано: (2011)

Superfluidity of a condensate with np pairing correlations in asymmetric nuclear matter
за авторством: Akhiezer, A.I., та інші
Опубліковано: (2001)

Mathematical modeling of neutron induced fission of 237Np nucleus
за авторством: C. Oprea, та інші
Опубліковано: (2022)

Mathematical modeling of neutron induced fission of 237Np nucleus
за авторством: C. Oprea, та інші
Опубліковано: (2022)

A criterion for Banach manifolds to be finite-dimensional
за авторством: Savkin, V. I., та інші
Опубліковано: (1995)

On a criterion of rationality for a series in orthogonal polynomials
за авторством: Buslaev, V. I., та інші
Опубліковано: (2010)

On one criterion of constancy of a complex function
за авторством: Safonov, V. M., та інші
Опубліковано: (1999)

On Completeness of a System of Functions in an Angular Domain
за авторством: Dilnyi, V. M., та інші
Опубліковано: (2001)

N.P. Kondakov Role in the Funds Museum of Fine Arts of the Novorossiysks Imperial University
за авторством: S. Zheliaskov, та інші
Опубліковано: (2014)

Homotopical criterion of point mapping
за авторством: Kompaniets, V. P., та інші
Опубліковано: (1966)

A criterion for Banach manifolds with a separable model to be finite-dimensional
за авторством: Savkin, V. I., та інші
Опубліковано: (1994)

Cross sections of the 3H(d, t)np reaction at the 37 MeV deuteron beam energy
за авторством: O. O. Beliuskina, та інші
Опубліковано: (2014)

On complete and quasi-complete two-criteria optimization problems on graphs
за авторством: V. A. Perepelitsa, та інші
Опубліковано: (2018)

Chiphragmalithus alatus zone (NP15) in the sediments of the Kyiv Regional Stage, N Ukraine
за авторством: E. A. Soljanik
Опубліковано: (2013)

On zeros of functions analytic in a half plane and completeness of systems of exponents
за авторством: Vynnyts’kyi, B. V., та інші
Опубліковано: (1994)

A criterion of solvability of resonant equations and construction of their solutions
за авторством: Boichuk, О. A., та інші
Опубліковано: (2026)

On Abelian completely $M(m)$-factorizable groups
за авторством: Tsybanev, M. V., та інші
Опубліковано: (1971)

Problem of completeness of maximal topological groups
за авторством: Arnautov , V. I., та інші
Опубліковано: (1991)

The Hoyle state of 12C nucleus in the 14N(γ, np)3α reaction
за авторством: S. N. Afanasiev
Опубліковано: (2022)

The Hoyle state of 12C nucleus in the 14N(γ, np)3α reaction
за авторством: S. M. Afanasiev
Опубліковано: (2022)

Academician N.P . Semenenko: prominent science organizerin Ukraine ( On the occasion of the 110th anniversary)
за авторством: A. N. Donskoj, та інші
Опубліковано: (2016)

A stability criterion for periodic solutions of two-dimensional discontinuous dynamical systems
за авторством: Urmanchev, V. I., та інші
Опубліковано: (1999)

Differentiality criterion after Belinsky and its consequences
за авторством: Ryazanov , V. I., та інші
Опубліковано: (1992)

On invariant subspaces of completely continuous bisymmetrical operators
за авторством: Godіch, V. I., та інші
Опубліковано: (1966)

A Procedure of Complete Averaging for Fuzzy Differential Inclusions on a Finite Segment
за авторством: Plotnikov, A. V., та інші
Опубліковано: (2015)

A Remark on the Completeness of Systems of Exponentials with Weight in $L^2(ℝ)$
за авторством: Vynnyts’kyi, B. V., та інші
Опубліковано: (2000)

On the Sobolev problem in the complete scale of Banach spaces
за авторством: Los’, V. M., та інші
Опубліковано: (1999)

Sobolev problem in the complete scale of Banach Spaces
за авторством: Roitberg, Ya. A., та інші
Опубліковано: (1996)

An example of a complete orthonormal system in a Hilbert space of generalized functions
за авторством: Gladkivs’ka, O. V., та інші
Опубліковано: (1997)

Isomeric yield ratios and mean angular momenta of photofission fragments of 235U, 237 Np and 239Pu
за авторством: I. N. Vishnevskij, та інші
Опубліковано: (2015)

Criterion for convexity of a domain of a Euclidean space
за авторством: Vyhovs'ka, I. Yu., та інші
Опубліковано: (2008)

Algebras of symmetries of completely integrable dynamic systems
за авторством: Samoilenko , V. Gr., та інші
Опубліковано: (1988)

A theorem on the structure of a complete set of conformal-like series of conserved quantities for massless fields
за авторством: Simulik, V. M., та інші
Опубліковано: (1997)

Axially symmetric vibrations of a complete conical shell
за авторством: V. A. Trotsenko, та інші
Опубліковано: (2020)

Complete asymptotic decomposition of the sojourn probability of a diffusion process in thin domains with moving boundaries
за авторством: Gasanenko, V. A., та інші
Опубліковано: (1999)

On the completeness of oscillation spaces
за авторством: Ben Slimane, M.
Опубліковано: (2005)

A criterion of solvability of resonant equations and construction of their solutions
за авторством: O. A. Boichuk, та інші
Опубліковано: (2019)