RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2012, том 13, выпуск 1, страницы 46–53 (Mi cheb12)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе

В. Г. Дурнев, О. В. Зеткина

Ярославский государственный университет им. П. Г. Демидова

Аннотация: Рассматривается проблема разрешимости в свободной группе $F_2$ ранга 2 со свободными образующими $a$ и $b$ для уравнений вида $w(x_1, ..., x_n) = g$, где $w(x_1, ..., x_n)$ – групповое слово в алфавите неизвестных $\{ x_1, …, x_n, …\}$, а $g$ – групповое слово в алфавите $\{ a, b \}$ свободных образующих группы $F_2$.
Устанавливается $NP$-трудность проблемы разрешимости в этой группе для уравнений вида $w(x_1, …, x_n) = a b a^{-1} b^{-1}$.
Показана полиномиальная разрешимость проблемы разрешимости для уравнений вида $w(x_1, ..., x_n)=g$, где $g$ – групповое слово длины меньше 4 в алфавите $\{ a, b \}$ свободных образующих группы $F_2$.

Полный текст: PDF файл (343 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 510.53+512.54.0+512.54.03+512.54.05+512.543.72
Поступила в редакцию: 18.05.2012

Образец цитирования: В. Г. Дурнев, О. В. Зеткина, “NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе”, Чебышевский сб., 13:1 (2012), 46–53

Цитирование в формате AMSBIB
\RBibitem{DurZet12}
\by В.~Г.~Дурнев, О.~В.~Зеткина
\paper NP-трудность проблемы разрешимости для уравнений с простой правой частью в свободной группе
\jour Чебышевский сб.
\yr 2012
\vol 13
\issue 1
\pages 46--53
\mathnet{http://mi.mathnet.ru/cheb12}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb12
  • http://mi.mathnet.ru/rus/cheb/v13/i1/p46

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. Г. Дурнев, О. В. Зеткина, “Некоторые результаты, полученные в Ярославском отделении алгебраической школы М. Д. Гриндлингера”, Чебышевский сб., 15:4 (2014), 5–31  mathnet
  • Просмотров:
    Эта страница:188
    Полный текст:73
    Литература:22
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020