Buchumschlag

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:

Bibliographische Detailangaben
Datum:	1998
Hauptverfasser:	Bulitko, V. V., Bulitko, V. K., Булитко, В. В., Булитко, В. К.
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

Ähnliche Einträge

Solvability of NP-complete problems
von: O. A. Vahis, et al.
Veröffentlicht: (2022)

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

NP-hardness of collective pursuiting optimization problems
von: Pashko, S.V.
Veröffentlicht: (2025)

Superfluidity of a condensate with np pairing correlations in asymmetric nuclear matter
von: Akhiezer, A.I., et al.
Veröffentlicht: (2001)

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

Mathematical modeling of neutron induced fission of 237Np nucleus
von: C. Oprea, et al.
Veröffentlicht: (2022)

Mathematical modeling of neutron induced fission of 237Np nucleus
von: C. Oprea, et al.
Veröffentlicht: (2022)

A criterion for Banach manifolds to be finite-dimensional
von: Savkin, V. I., et al.
Veröffentlicht: (1995)

On a criterion of rationality for a series in orthogonal polynomials
von: Buslaev, V. I., et al.
Veröffentlicht: (2010)

On one criterion of constancy of a complex function
von: Safonov, V. M., et al.
Veröffentlicht: (1999)

On Completeness of a System of Functions in an Angular Domain
von: Dilnyi, V. M., et al.
Veröffentlicht: (2001)

Homotopical criterion of point mapping
von: Kompaniets, V. P., et al.
Veröffentlicht: (1966)

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

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

On complete and quasi-complete two-criteria optimization problems on graphs
von: V. A. Perepelitsa, et al.
Veröffentlicht: (2018)

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

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

A criterion of solvability of resonant equations and construction of their solutions
von: Boichuk, О. A., et al.
Veröffentlicht: (2026)

Chiphragmalithus alatus zone (NP15) in the sediments of the Kyiv Regional Stage, N Ukraine
von: E. A. Soljanik
Veröffentlicht: (2013)

Problem of completeness of maximal topological groups
von: Arnautov , V. I., et al.
Veröffentlicht: (1991)

On Abelian completely $M(m)$-factorizable groups
von: Tsybanev, M. V., et al.
Veröffentlicht: (1971)

Differentiality criterion after Belinsky and its consequences
von: Ryazanov , V. I., et al.
Veröffentlicht: (1992)

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

Criterion for convexity of a domain of a Euclidean space
von: Vyhovs'ka, I. Yu., et al.
Veröffentlicht: (2008)

On invariant subspaces of completely continuous bisymmetrical operators
von: Godіch, V. I., et al.
Veröffentlicht: (1966)

A Procedure of Complete Averaging for Fuzzy Differential Inclusions on a Finite Segment
von: Plotnikov, A. V., et al.
Veröffentlicht: (2015)

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

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

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

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

Axially symmetric vibrations of a complete conical shell
von: V. A. Trotsenko, et al.
Veröffentlicht: (2020)

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

On the Sobolev problem in the complete scale of Banach spaces
von: Los’, V. M., et al.
Veröffentlicht: (1999)

Sobolev problem in the complete scale of Banach Spaces
von: Roitberg, Ya. A., et al.
Veröffentlicht: (1996)

A criterion of solvability of resonant equations and construction of their solutions
von: O. A. Boichuk, et al.
Veröffentlicht: (2019)

Algebras of symmetries of completely integrable dynamic systems
von: Samoilenko , V. Gr., et al.
Veröffentlicht: (1988)

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

A criterion of elementary divisor domain for distributive domains
von: V. Bokhonko, et al.
Veröffentlicht: (2017)

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

A Kolmogorov type criterion for the best approximating operator
von: Tyrygin, I. Ya., et al.
Veröffentlicht: (1993)