О генерической сложности проблемы распознавания гамильтоновых путей

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы распознавания гамильтоновых путей	634 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/53/8

Title: О генерической сложности проблемы распознавания гамильтоновых путей
Title: The general complexity of the problem to recognize Hamiltonian paths
Creator: Рыбалов, Александр Николаевич
Date: 2021
DOI: 10.17223/20710410/53/8
Description: Изучается генерическая сложность проблемы распознавания гамильтоновых путей в конечных графах. Путь в графе называется гамильтоновым, если он проходит через все вершины ровно по одному разу. Доказывается, что при условии P = NP и P = BPP для этой проблемы не существует полиномиального сильно генерического алгоритма.

Created: 14-12-2021

332 Visitors

161 Hits

175 Downloads

Журналы ТГУ О генерической сложности проблемы распознавания гамильтоновых путей