О генерической сложности решения уравнений над натуральными числами со сложением Научная публикация
| Журнал |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Вых. Данные | Год: 2024, Номер: 64, Страницы: 72-78 Страниц : 7 DOI: 10.17223/20710410/64/6 | ||
| Ключевые слова | генерическая сложность, линейные уравнения, натуральные числа | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Реферат:
Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р ≠ NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.
Библиографическая ссылка:
Рыбалов А.Н.
О генерической сложности решения уравнений над натуральными числами со сложением
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. №64. С.72-78. DOI: 10.17223/20710410/64/6 WOS РИНЦ OpenAlex
О генерической сложности решения уравнений над натуральными числами со сложением
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. №64. С.72-78. DOI: 10.17223/20710410/64/6 WOS РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 10 янв. 2024 г. |
| Опубликована в печати: | 4 июн. 2024 г. |
| Опубликована online: | 4 июн. 2024 г. |
Идентификаторы БД:
| Web of science: | WOS:001320166600007 |
| РИНЦ: | 67349993 |
| OpenAlex: | W4403100135 |