Сводимость - задача
Cтраница 1
Установленная сводимость задачи со сдвигом к задаче Римана позволяет формулировать результат. [1]
Рассмотрим теперь методы сводимости задач поиска кратчайших маршрутов в гиперсетях к аналогичным задачам на графах и гиперграфах. [2]
 |
Иллюстрация к получению нижней оценки сложности решения задачи ТРИАНГУЛЯЦИЯ. [3] |
Проведенный анализ позволил установить сводимость задач, представленную на рис. 5.6. Учитывая, что в рамках модели деревьев вычислений обе задачи ЕДИНСТВЕННОСТЬ ЭЛЕМЕНТОВ и СОРТИРОВКА - на множестве из N элементов имеют нижнюю оценку сложности Q ( NlogN), имеет место следующая теорема. [4]
В настоящей работе мы изучаем сводимость задачи факторизации к задаче Диффи-Хеллмана. Говоря неформально, наш основной результат ( теорема 1) означает следующее. При этом максимальное время работы алгоритма В на входе п превосходит максимальное время работы алгоритма А для задачи Диффи-Хеллмана по модулю п лишь в полиномиальное от суммы длин элементов п число раз. В частности, если алгоритм А полиномиален, то и алгоритм В полиномиален. [5]
Копта, может быть установлена прямая сводимость задачи Гильберта к задаче Римана. Для других контуров такой непосредственной связи не существует и она может быть установлена лишь при помощи конформного отображения соответствующих областей на круг или полуплоскость. [6]
Теперь мы подготовлены к тому, чтобы доказать сводимость задачи Гильберта к задаче Римана. [7]
Теперь мы подготовлены к тому, чтобы доказать сводимость задачи Гильберта к задаче Рнмапа. [8]
Утверждения () и () позволяют без труда доказать сформулированную выше теорему о сводимости задач о перчатках к задачам о чулках, поскольку выбор перчаток на любую из рук представляет собой независимую задачу. Поскольку должно быть одинаковое число правых и левых перчаток любого цвета, то обе независимые задачи о ( левых и правых) перчатках сводятся к одной и той же задаче о чулках. [9]
Сводимость играет большую роль для обеих из указанных проблем. Сводимость задач обычно используется для того, чтобы показать, разрешима ли задача или неразрешима. Наш подход к теории разрешимости [69, 200] основан главным образом на работах Тьюринга и его модели вычислений - машине Тьюринга. Значение машины Тьюринга состоит в том, что она служит разумным представлением вычислительной машины, и можно показать1), что не существует алгоритма, который бы решал определенные проблемы машины Тьюринга, в частности проблему остановки. На основе этого был найден ряд неразрешимых задач. И важность этой теории - в том, что невозможно создать программу для ЭВМ, которая бы решала эти задачи. Следовательно, для целей практического анализа необходимо избежать этих неразрешимых задач, иначе вопросы анализа не получат ответа. [10]
С композицией связывается некоторый орграф, дуги которого проводятся на основе сводимости задач. Эквивалентным задачам отвечают сильно связанные компоненты ориентированного графа. Этот орграф порождает декомпозицию задач, свойства которой определяются максимальным бесконтурным графом. [11]
В тех случаях, когда решение дается в замкнутой форме, соответствующие формулы приводятся полностью, но когда задача приводится к решению интегральных уравнений, ядра последних, как правило, не выписываются. Так делается, например, в главах III и VII при регуляризации особых уравнений, в главе V при сведении общих краевых задач к интегральным уравнениям. Устанавливается лишь факт сводимости задачи к уравнению и указывается процесс получения последнего. Читатель, усвоивший принципы теории, при решении практических задач легко составит сам соответствующее уравнение. [12]
Для решения этой задачи возможны различные пути. Можно, например, обобщить данное в главе IV решение4 задачи Гильберта на случай разрывных коэффициентов. Второй способ заключается в использовании установленной в § 30 сводимости задачи Гильберта к задаче Римана. [13]
Важной проблемой в теории протоколов распределения ключей типа Диффи-Хеллмана ( см. [4]) является проблема доказательства сходимости какой-либо предположительно трудной вычислительной задачи ( например, задачи дискретного логарифмирования или факторизации целых чисел) к задаче Диффи-Хеллмана, т.е. к задаче вычисления общего секретного ключа по данной открытой информации в некотором протоколе типа Диффи Хеллмана. Если такая сводимость имеет место, то из сложности исходной задачи вытекает стойкость соответствующего протокола. В работах ден Бура [3] и Маурера [5] доказана сводимость задачи дискретного логарифмирования к задаче Диффи-Хеллмана при некоторых дополнительных предположениях. Однако при полиномиальной сложности последней задачи эта оценка дает лишь субэкспоненциальную, а не полиномиальную верхнюю границу сложности задачи дискретного логарифмирования. В работах Шмуели [7] и МакКарли [6] изучается сводимость задачи факторизации п к задаче Диффи-Хеллмана по модулю п, где п является произведением двух различных простых чисел. К сожалению, автору недоступна работа [7]; в [6] приведен с наброском доказательства без ссылки на источник некоторый результат Шмуели, относящийся к вышеуказанной проблеме. При этом, однако, результат Шмуели ( в том виде, как он приведен в [6]) не позволяет утверждать, что если алгоритм А полиномиален и имеет не пренебрежимо малую вероятность успеха, то и алгоритм В полиномиален. [14]
Важной проблемой в теории протоколов распределения ключей типа Диффи-Хеллмана ( см. [4]) является проблема доказательства сходимости какой-либо предположительно трудной вычислительной задачи ( например, задачи дискретного логарифмирования или факторизации целых чисел) к задаче Диффи-Хеллмана, т.е. к задаче вычисления общего секретного ключа по данной открытой информации в некотором протоколе типа Диффи Хеллмана. Если такая сводимость имеет место, то из сложности исходной задачи вытекает стойкость соответствующего протокола. В работах ден Бура [3] и Маурера [5] доказана сводимость задачи дискретного логарифмирования к задаче Диффи-Хеллмана при некоторых дополнительных предположениях. Однако при полиномиальной сложности последней задачи эта оценка дает лишь субэкспоненциальную, а не полиномиальную верхнюю границу сложности задачи дискретного логарифмирования. В работах Шмуели [7] и МакКарли [6] изучается сводимость задачи факторизации п к задаче Диффи-Хеллмана по модулю п, где п является произведением двух различных простых чисел. К сожалению, автору недоступна работа [7]; в [6] приведен с наброском доказательства без ссылки на источник некоторый результат Шмуели, относящийся к вышеуказанной проблеме. При этом, однако, результат Шмуели ( в том виде, как он приведен в [6]) не позволяет утверждать, что если алгоритм А полиномиален и имеет не пренебрежимо малую вероятность успеха, то и алгоритм В полиномиален. [15]
Страницы: 1