Cover Image

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:

Bibliographic Details
Date:	1998
Main Authors:	Bulitko, V. V., Bulitko, V. K., Булитко, В. В., Булитко, В. К.
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 Zhurnal

Similar Items

Solvability of NP-complete problems
by: O. A. Vahis, et al.
Published: (2022)

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

NP-hardness of collective pursuiting optimization problems
by: Pashko, S.V.
Published: (2025)

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

Superfluidity of a condensate with np pairing correlations in asymmetric nuclear matter
by: Akhiezer, A.I., et al.
Published: (2001)

Mathematical modeling of neutron induced fission of 237Np nucleus
by: C. Oprea, et al.
Published: (2022)

Mathematical modeling of neutron induced fission of 237Np nucleus
by: C. Oprea, et al.
Published: (2022)

A criterion for Banach manifolds to be finite-dimensional
by: Savkin, V. I., et al.
Published: (1995)

On a criterion of rationality for a series in orthogonal polynomials
by: Buslaev, V. I., et al.
Published: (2010)

On one criterion of constancy of a complex function
by: Safonov, V. M., et al.
Published: (1999)

On Completeness of a System of Functions in an Angular Domain
by: Dilnyi, V. M., et al.
Published: (2001)

N.P. Kondakov Role in the Funds Museum of Fine Arts of the Novorossiysks Imperial University
by: S. Zheliaskov, et al.
Published: (2014)

Homotopical criterion of point mapping
by: Kompaniets, V. P., et al.
Published: (1966)

A criterion for Banach manifolds with a separable model to be finite-dimensional
by: Savkin, V. I., et al.
Published: (1994)

Cross sections of the 3H(d, t)np reaction at the 37 MeV deuteron beam energy
by: O. O. Beliuskina, et al.
Published: (2014)

On complete and quasi-complete two-criteria optimization problems on graphs
by: V. A. Perepelitsa, et al.
Published: (2018)

Chiphragmalithus alatus zone (NP15) in the sediments of the Kyiv Regional Stage, N Ukraine
by: E. A. Soljanik
Published: (2013)

On zeros of functions analytic in a half plane and completeness of systems of exponents
by: Vynnyts’kyi, B. V., et al.
Published: (1994)

A criterion of solvability of resonant equations and construction of their solutions
by: Boichuk, О. A., et al.
Published: (2026)

On Abelian completely $M(m)$-factorizable groups
by: Tsybanev, M. V., et al.
Published: (1971)

Problem of completeness of maximal topological groups
by: Arnautov , V. I., et al.
Published: (1991)

The Hoyle state of 12C nucleus in the 14N(γ, np)3α reaction
by: S. N. Afanasiev
Published: (2022)

The Hoyle state of 12C nucleus in the 14N(γ, np)3α reaction
by: S. M. Afanasiev
Published: (2022)

Academician N.P . Semenenko: prominent science organizerin Ukraine ( On the occasion of the 110th anniversary)
by: A. N. Donskoj, et al.
Published: (2016)

A stability criterion for periodic solutions of two-dimensional discontinuous dynamical systems
by: Urmanchev, V. I., et al.
Published: (1999)

Differentiality criterion after Belinsky and its consequences
by: Ryazanov , V. I., et al.
Published: (1992)

On invariant subspaces of completely continuous bisymmetrical operators
by: Godіch, V. I., et al.
Published: (1966)

A Procedure of Complete Averaging for Fuzzy Differential Inclusions on a Finite Segment
by: Plotnikov, A. V., et al.
Published: (2015)

A Remark on the Completeness of Systems of Exponentials with Weight in $L^2(ℝ)$
by: Vynnyts’kyi, B. V., et al.
Published: (2000)

On the Sobolev problem in the complete scale of Banach spaces
by: Los’, V. M., et al.
Published: (1999)

Sobolev problem in the complete scale of Banach Spaces
by: Roitberg, Ya. A., et al.
Published: (1996)

An example of a complete orthonormal system in a Hilbert space of generalized functions
by: Gladkivs’ka, O. V., et al.
Published: (1997)

Isomeric yield ratios and mean angular momenta of photofission fragments of 235U, 237 Np and 239Pu
by: I. N. Vishnevskij, et al.
Published: (2015)

Criterion for convexity of a domain of a Euclidean space
by: Vyhovs'ka, I. Yu., et al.
Published: (2008)

Algebras of symmetries of completely integrable dynamic systems
by: Samoilenko , V. Gr., et al.
Published: (1988)

A theorem on the structure of a complete set of conformal-like series of conserved quantities for massless fields
by: Simulik, V. M., et al.
Published: (1997)

Axially symmetric vibrations of a complete conical shell
by: V. A. Trotsenko, et al.
Published: (2020)

Complete asymptotic decomposition of the sojourn probability of a diffusion process in thin domains with moving boundaries
by: Gasanenko, V. A., et al.
Published: (1999)

On the completeness of oscillation spaces
by: Ben Slimane, M.
Published: (2005)

A criterion of solvability of resonant equations and construction of their solutions
by: O. A. Boichuk, et al.
Published: (2019)