|
Эта публикация цитируется в 10 научных статьях (всего в 10 статьях)
К проблеме разрешимости уравнений с одним коэффициентом
В. Г. Дурнев Ярославский государственный университет им. П. Г. Демидова
Аннотация:
Доказывается, что общая проблема разрешимости уравнений в свободной группе полиномиально сводима к проблеме разрешимости уравнений вида $w(x_1,\dots,x_n)=g$, где $g$ – коэффициент, т.е. элемент группы, а $w(x_1,\dots,x_n)$ – групповое слово в алфавите неизвестных. Устанавливается NP-полнота проблемы разрешимости в свободной полугруппе уравнений вида $w(x_1,\dots,x_n)=g$, где $w(x_1,\dots,x_n)$ – полугрупповое слово в алфавите неизвестных, а $g$ – элемент свободной полугруппы.
Библиография: 19 названий.
Поступило: 30.06.1994
Образец цитирования:
В. Г. Дурнев, “К проблеме разрешимости уравнений с одним коэффициентом”, Матем. заметки, 59:6 (1996), 832–845; Math. Notes, 59:6 (1996), 601–610
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm1782https://doi.org/10.4213/mzm1782 https://www.mathnet.ru/rus/mzm/v59/i6/p832
|
Статистика просмотров: |
Страница аннотации: | 410 | PDF полного текста: | 188 | Список литературы: | 39 | Первая страница: | 1 |
|