|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О сложности задачи выполнимости мультилинейных форм над конечным полемстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАКСтатья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
- Автор: Селезнева С.Н.
- Журнал: Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика
- Номер: 2
- Год издания: 2017
- Издательство: Изд-во Моск. ун-та
- Местоположение издательства: М.
- Первая страница: 30
- Последняя страница: 37
- Аннотация: В работе рассматриваются мультилинейные формы над конечными полями. Мультилинейной формой над некоторым полем называется произведение, в котором каждый сомножитель является суммой переменных или элементов этого поля. Каждая мультилинейная форма определяет некоторую функцию над этим полем. Мультилинейная форма называется выполнимой, если она задает ненулевую функцию. Показана NP-полнота задачи распознавания выполнимости мультилинейных форм над каждым конечным полем из q элементов при q \ge 3. Доказана теорема, разделяющая случаи полиномиальности и NP-полноты задачи выполнимости мультилинейных форм при каждом возможном q \ge 3.
- Добавил в систему: Селезнева Светлана Николаевна
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | selezn-v2-2017.pdf | 259,5 КБ | 15 декабря 2017 [selezn@cs.msu.su] |