2018
Том 70
№ 9

Всі номери

О критерии $NP$-полноты

Булитко В. В., Булитко В. К.

Повний текст (.pdf)


Абстракт

Розглядається проблема побудови критерии повних множин відносно поліноміальпо обмежених звідпостей. Запропоновані нестандартний опис множин класу $NP$, коротке доведення відомої теореми Кука та деякий критерій $NP$-повноти.

Англомовна версія (Springer): Ukrainian Mathematical Journal 50 (1998), no. 12, pp 1924-1928.

Зразок цитування: Булитко В. В., Булитко В. К. О критерии $NP$-полноты // Укр. мат. журн. - 1998. - 50, № 12. - С. 1686–1691.

Повний текст