О проблеме P=NP в некоторых кольцах Научная публикация
| Журнал |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Вых. Данные | Год: 2025, Том: 21, Номер: 1, Страницы: 683-691 Страниц : 9 DOI: 10.33048/semi.2025.22.045 | ||
| Ключевые слова | computational complexity, P vs NP, ring, nilpotent element | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Российский научный фонд | 25-11-20023 |
Реферат:
We consider a computational complexity theory over arbitrary algebraic structures based on an approach to generalized computability developed by Ashaev, Belyaev and Myasnikov. Let R be a ring with a nilpotent element η of nilpotency index k > 1 such that η is an algebraic element over Z of degree k. We prove that analogs of the classical computational complexity classes P and NP over R are di erent.
Библиографическая ссылка:
Рыбалов А.Н.
О проблеме P=NP в некоторых кольцах
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.21. №1. С.683-691. DOI: 10.33048/semi.2025.22.045 WOS
О проблеме P=NP в некоторых кольцах
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.21. №1. С.683-691. DOI: 10.33048/semi.2025.22.045 WOS
Даты:
| Поступила в редакцию: | 25 мая 2025 г. |
| Опубликована в печати: | 4 июл. 2025 г. |
| Опубликована online: | 4 июл. 2025 г. |
Идентификаторы БД:
| Web of science: | WOS:001540698300002 |
Цитирование в БД:
Пока нет цитирований