Cтраница 2
В этой работе теория сложности применяется к сетям Петри. Для нескольких задач в сетях Петри, включая достижимость, активность и безопасность, даны границы времени и объема памяти. Показано, что живучесть сводима к достижимости. Результаты по сложности даны как для сетей Петри, так и для автоматов, маркированных графов и сетей Петри со свободным выбором. [16]
Далее, в теории сложности задач выбора вводят понятия эффективных и неэффективных алгоритмов. [17]
Следовательно, в теории сложности алгебраических и комбинаторных задач ищется алгоритм, который находит a S ( f) и обладает минимальной комбинаторной сложностью. [18]
Из области приложений теории сложности к обработке данных мы рассмотрим известнейший пример, а именно сортировку. [19]
Самая серьезная проблема в теории сложности, отделяющая эту теорию от анализа алгоритмов, - доказательство нижних оценок сложности отдельных задач. Есть нечто вызывающее большое удовлетворение, когда удается доказать, что задача, требующая ответа да-нет, не может быть решена за п или п2 или 2п шагов независимо от того, какой алгоритм применяется для ее решения. В доказательстве нижних оценок удалось многого достичь, но остались открытыми еще более важные и обескураживающие вопросы. [20]
В качестве вспомогательных в теории аналитической сложности может потребоваться решение задач алгебраической сложности. Информационные операторы часто являются неполными. [21]
Дан обзор результатов по теории итеративной сложности и некоторые исторические комментарии. Вводится термин аналитическая вычислительная сложность. [22]
Одним из важнейших достижений алгоритмической теории сложности является возможность количественной оценки мощности бесконечных множеств и формирование нового научного направления для решения проблемы табулирования непрерывных функций. [23]
Первоначально разрабатываемую теорию называли теорией аналитической сложности, затем / - сложности и, наконец, теорией информационной сложности. [24]
Я благодарен своим коллегам по теории сложности в Торонто за многие полезные замечания и предложения, особенно Аллану Бородину, Иоахиму фон цур Гатену, Сильвио Микали и Чарльзу Ракову. [25]
Другой важной темой, которую теория сложности унаследовала от теории вычислимости, является различие между способностью решить задачу и способностью проверить решение. Даже несмотря на то, что не существует общего метода нахождения решения для диофантова уравнения, легко проверить предлагаемое решение. Например, чтобы проверить, является ли х 3, у 2, z - 1 решением приведенного выше диофантова уравнения, просто подставляют в него эти значения и выполняют арифметические действия. [26]
Одна из основных проблем в теории аналитической сложности заключается в отыскании для данной задачи наиболее подходящей информации. [27]
Тем не менее в рамках алгоритмической теории сложности получены результаты, которые непосредственно можно использовать для построения алгоритмов принятия оперативных решений. [28]
В данной статье мы переводим теорию сложности на язык алгебраической геометрии. [29]
Таким образом, нам необходима такая теория сложности, которая позволяет нам установить и доказать, что некоторое вычисление неосуществимо практически всегда. [30]