В. Ю. Попов, “Об NP-полноте проблемы создания словаря”, Матем. тр., 2006, том 9, номер 1,страницы 117

Об NP-полноте проблемы создания словаря

В. Ю. Попов

Уральский государственный университет им. А. М. Горького

Аннотация: Рассмотрена проблема построения словаря. Доказано, что эта проблема является NP-полной. Рассмотрена также параметрическая сложность этой проблемы.

Ключевые слова и фразы: построение словаря, NP-полнота, параметрическая сложность.

УДК: 512+519.4

Статья поступила: 30.11.2004

Англоязычная версия: Siberian Advances in Mathematics, 2006, 16:3, 115–125

Реферативные базы данных: