Cтраница 2
Нужно отметить, что предпринятое здесь теоретико-групповое построение интегрируемых систем тесно смыкается с алгебро-геомет-рическим подходом работ [13,14,18,19]: автором и М.А.Семеновым-Тян - Шанским доказано, что задача факторизации, к которой сводится решение уравнений движения, в свою очередь решается в терминах функции Бейкера-Ахиезера, связанной со спектральной кривой. [16]
При этом можно считать, что число п взаимно просто с дискриминантом многочлена 4х3 ал: 6, иначе мы получим нетривиальный делитель п и решим тем самым задачу факторизации. [17]
В третьей главе подробно излагается теория сингулярных интегральных операторов на замкнутом контуре с непрерывными коэффициентами. Несколько параграфов этой главы посвящены задаче факторизации функций. [18]
Заметим, что их стойкость основана на сложности задачи факторизации целых чисел. [19]
Следует, однако, отметить, что использование соотношений (3.64) не всегда приводит к операторному представлению функции с наименьшим числом операторов. Задача представления функции в форме с минимальным числом операторов аналогична задаче факторизации булевых функций, которая состоит в получении абсолютно минимальных форм представления функций. Известные к настоящему времени способы факторизации не намного эффективнее перебора всех возможных суперпозиций, состоящих из двух, трех и более операторов, до тех пор, пока не будут получены представления функций с абсолютно минимальным числом операторов. Вполне естественно, что такие способы из-за своей громоздкости не имеют практического значения. Поэтому задача факторизации решается приближенно путем вынесения за скобки некоторых переменных в МДНФ функции, хотя доказано, что таким способом не всегда удается получить абсолютно минимальное представление функций. [20]
Хорошо известно ( см., напршлер, Щ), что решение пространственно-двумерных уравнении типа КП приводит к нелокальной задаче Римана. Мы покажем, что в рамках общего теоретико-группового подхода D - ] задача факторизации в группе операторов, или в группе ( г1к о), также естественно связана с уравнениями типа ХП. Слошюстъ этой связи обусловлена тем, что не существует груп-ш, отвечающей основной алгебре Ли ( Л, - алгебре всех псевдодифференциальных символов. [21]
Эта задача считается сложной настолько, что на предположении о трудности ее решения основываются практические алгоритмы криптографии. С теоретической точки зрения положение несколько хуже: неизвестно ни сведение к задаче факторизации задач из класса NP, ни другие прямые свидетельства в пользу ее сложности. Слово прямые взято в кавычки из-за того, что в настоящее время неизвестен ответ на вопрос Р NP. Таким образом, предположение о сложности задачи факторизации пополняет и без того обильную коллекцию недоказанных гипотез в вычислительной теории сложности. Количество таких гипотез хочется по возможности уменьшать. В этом и состоит основная ценность результата Шора - если совершить один акт веры и уверовать в сложность задачи факторизации, то необходимость в еще одном акте веры ( относительно больших вычислительных возможностей квантового компьютера) отпадает. [22]
Несмотря на такой произвол в выборе функции Грина и получающихся с ее помощью интегральных уравнений, все интегральные уравнения приводят к одной и той же задаче факторизации, являющейся основой в Mei оде Винера - Хопфа. Во всех случаях функция / С ( а) которую надо представить в виде К ( к) К ( а), оказывается одной и той же. [23]
Устанавливаются признаки односторонней обратимости этих операторов. Приводятся формулы для решения однородных и неоднородных уравнений. Подробно исследуется задача факторизации Рассматривается одао абстрактное обобщение сингулярных интегральных операторов. [24]
Основное место в книге отведено теории линейных одномерных сингулярных интегральных операторов о непрерывными и разрывными коэффициентами в различных функциональных пространствах. При весьма общих ограничениях выясняются условия обратимости таких операторов, ввд обратного оператора, структура ядра и коядра. Подробно рассматривается задача факторизации функций относительно контура. [25]
Способ определения параметров формирующего фильтра на основе выражения (5.69) может быть использовн и для получения случайных последовательностей, учитывая материал разд. Этот путь принципиально может быть распространен и на генерацию векторных процессов и последовательностей. Однако трудности решения задач факторизации в матричном варианте не позволяют считать способ получения векторных процессов на основе (5.69) перспективным. [26]
Желание получить мощное факторизующее устройство ( с криптографическими приложениями) расценивается как одно из первичных побуждений к созданию квантового компьютера. На самом деле то, что задача факторизации считается сегодня особенно важной, представляется мне исторической случайностью. [27]
В этой статье мы обсудили один алгоритм, приводящий к экспоненциальному ускорению по сравнению с обычными методами - ффективное вычисление периода длинной последовательности. Этот алгоритм был применен к традиционной задаче вычислительной математики - задаче факторизации только благодаря пониманию глу-окой структуры, лежащей в основе этой проблемы. [28]
В этом параграфе вводятся бесконечномерные алгебры Ли и их разложения, играющие в дальнейшем основную роль. Описание нужных нам орбит и гамильтоновой механики на них не требует привлечег ния соответствующих бесконечномерных групп Ли - групп токов. Однако геометрическая конструкция § I позволяет выразить решение уравнений движения через решение задачи факторизации в группе. [29]
Наибольшее внимание привлекает класс сложности BQP ( Bounded-error Quantum Polynomial-time), содержащий задачи, решаемые полиномиальными по времени квантовыми машинами Тьюринга с большой надежностью. Класс сложности ВРР ( Bounded-error Probabilistic Polynomial-time) содержит задачи, решаемые полиномиальными по времени классическими вероятностными машинами Тьюринга с большой надежностью. Интерес к классу BQP вызван тем, что в 90 - х годах удалось построить эффективные ( надежные, полиномиальные по времени) квантовые алгоритмы для ряда задач, для которых эффективные ( полиномиальные по времени и надежные) классические алгоритмы неизвестны. Задача факторизации и близкая к ней задача дискретного логарифма имеют важную, но специфическую область применения - создание систем шифрования с открытым ключом. Отметим, что на сегодняшний день пока не найдены широкие области теории и практики вычислений, где квантовые алгоритмы имеют значительное преимущество по сравнению с классическими алгоритмами. Открытым вопросом является построение эффективного квантового алгоритма для NP полных задач или доказательство того, что это невозможно. [30]