О генерической сложности решения уравнений над натуральными числами со сложением Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Output data | Year: 2024, Number: 64, Pages: 72-78 Pages count : 7 DOI: 10.17223/20710410/64/6 | ||
| Tags | генерическая сложность, линейные уравнения, натуральные числа | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0003 |
Abstract:
Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р ≠ NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.
Cite:
Рыбалов А.Н.
О генерической сложности решения уравнений над натуральными числами со сложением
Прикладная дискретная математика (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
Dates:
| Submitted: | Jan 10, 2024 |
| Published print: | Jun 4, 2024 |
| Published online: | Jun 4, 2024 |
Identifiers:
| Web of science: | WOS:001320166600007 |
| Elibrary: | 67349993 |
| OpenAlex: | W4403100135 |