Название статьи:
NP-трудные задачи: автоматическое доказательство теорем и машины Тьюринга
Авторы: Мартьянов В.И., доктор физико-математических наук, профессор, профконсультант, Байкальский государственный университет, г. Иркутск, Российская Федерация,
martvliv@mail.ru В рубрике:
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, СИСТЕМНЫЙ АНАЛИЗ
Год: 2021 Том: 12 Номер журнала: 4
Страницы: 11-11
Тип статьи: Научная статья
УДК: 334+37
DOI: 10.17150/2411-6262.2021.12(4).11
Аннотация:
Предлагается использовать для решения NP-полных (трудных) задач модификацию методов удовлетворения ограничением [1, с. 54] (УО) включением автоматического доказательства теорем (АДТ), а программирования в ограничениях [1, с. 114] - генераций машин Тьюринга (МТ) [2, с. 222]. В настоящее время УО [1, с. 57] использует АДТ в усеченной форме (логическое программирование), а предлагается использовать метод инвариантных преобразований (МИП) [3, с. 572], который является полноценным АДТ. Кроме того, предлагается использовать методы УО для генерации МТ, решающих NP-трудные задачи, записанные на ленте МТ, что является расширением возможностей программирования в ограничениях [1, с. 118].
Ключевые слова: NP-трудные задачи, удовлетворение ограничениям, программирование в ограничениях, искусственный интеллект, автоматическое доказательства теорем
Список цитируемой литературы: - Щербина О.А. Удовлетворение ограничений и программирование в ограничениях / О.А. Щербина // Интеллектуальные системы. - 2011. - Т. 15, вып. 1-4. - С. 53-170.
- Мальцев А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. - Москва : Наука, 1965. - 392 с.
- Мартьянов В.И. Об инвариантных преобразованиях формул / В.И. Мартьянов // Математические заметки. - 1984. - Т. 36, вып. 4. - С. 571-581.
- Van Hentenrick P. Constraint Satisfaction in Logic Programming / P. van Hentenrick. - London : The MIT Press, 1989. - 356 p.
- Мартьянов В.И. Комбинаторные задачи высокой сложности и анализ плоских контурных изображений / В.И. Мартьянов, М.Д. Каташевцев // Известия Иркутского государственного университета. Серия: Математика. - 2013. - Т. 6, № 4. - С. 31-47.
- Ершов Ю.Л. Математическая логика : учеб. пособие / Ю.Л. Ершов, Е.А. Палютин. - Москва : Наука, 1987. - 336 с.
- Робинсон Дж. Машино-ориентированная логика, основанная на приципе резолюции / Дж. Робинсон // Кибернетический сборник (новая серия) / под ред. О.Б. Лупанова. - Москва, 1970. - Вып. 7. - С. 194-218.
- Мартьянов В.И. О реализации схем доказательств в методе инвариантных преобразований / В.И. Мартьянов, А.А. Xармеев, Н.П. Яковлев // Кибернетика. - 1988. - № 3. - С. 78-83.
- Александров С.Г. Применение системы АДТ для решения задач сетевого планирования / С.Г. Александров, В.И. Мартьянов // Интеллектуализация программных средств : сб. науч. тр. - Новосибирск, 1990. - С. 160-168.
- Мартьянов В.И. Планирование информационных потоков в иерархической системе / В.И. Мартьянов, В.В. Сухорутченко, В.В. Окунцов // Прикладные системы. - Москва, 1992. - С. 46-58.