О проблеме P=NP в некоторых кольцах Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2025, Volume: 21, Number: 1, Pages: 683-691 Pages count : 9 DOI: 10.33048/semi.2025.22.045 | ||
| Tags | computational complexity, P vs NP, ring, nilpotent element | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Russian Science Foundation | 25-11-20023 |
Abstract:
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.
Cite:
Рыбалов А.Н.
О проблеме 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
Dates:
| Submitted: | May 25, 2025 |
| Published print: | Jul 4, 2025 |
| Published online: | Jul 4, 2025 |
Identifiers:
| Web of science: | WOS:001540698300002 |
Citing:
Пока нет цитирований