Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

№16, Москва, 2007
Авторы: Косовский Н.К., Косовская Т.М.
Полиномиальность и NP-трудность задачи вычисления знака постоянного терма
Аннотация:
Доказывается, что задача вычисления значения знака постоянного терма в сигнатуре бN2; +, –, ·, /, -&,-с полиномиальна. В то же время добавление в эту сигнатуру функции возведения в квадрат превращает эту же задачу (вычисления знака постоянного терма) в NP-трудную. Здесь N2 – множество двоичных записей неотрицательных натуральных чисел. Операции -& и -∨ являются поразрядными операциями конъюнкции и дизъюнкции соответственно. Операция деления / всегда имеет второй аргумент, отличный от нуля, и используется только если результат является целым.
Ключевые слова:
NP-трудные задачи, класс FP, постоянный терм в заданной сигнатуре, схема в заданном базисе
Язык публикации: русский, страниц: 4 (с. 125-128)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст: Сведения об авторах:
  • Косовский Н.К.,  ,  Санкт-Петербургский государственный университет
  • Косовская Т.М.,  ,  Санкт-Петербургский государственный университет