Cтраница 1
Полиномиальный алгоритм в линейном программировании / / Докл. [1]
Приводятся полиномиальные алгоритмы решения задачи в следующих случаях: а) множество требований не упорядочено; б) граф редукции отношения строгого порядка является древовидным; в) М 2 при произвольном графе редукции отношения строгого порядка. В последних двух случаях предполагается, что длительности обслуживания требований соизмеримы. [2]
Существует ли полиномиальный алгоритм для следующей ва-дачи. Дано натуральное число я. Определить, является ли п простым ( составным) числом. [3]
Известно очень мало полиномиальных алгоритмов нахождения расписаний минимальной длины даже для тех случаев, когда наложены строгие ограничения на частичное упорядочение и времена выполнения заданий. Для начала мы будем считать, что все процессоры идентичны, следовательно, время выполнения задания Т на всех процессорах одно и то же. В сущности, имеются два случая, для которых известны полиномиальные алгоритмы: ( а) когда граф системы заданий является деревом и ( б) когда в системе имеются только два процессора. [4]
Для этого существует полиномиальный алгоритм, вычисляющий Х и DEP ( X), на основе которого выводится заключение F X - Y или F & X - У. [5]
Аппроксимацию на основе обобщенных полиномиальных алгоритмов для синтеза электронных схем использовать нельзя, так как в этом случае не гарантируется получение физически реализуемой передаточной функции. [6]
С другой стороны, полиномиальные алгоритмы позволяют делать такие прогнозы, поскольку полиномиальные функции значительно более адекватно оценивают время работы алгоритмов. [7]
Опишем сначала простой недетерминированный полиномиальный алгоритм для определения того, содержит ли С полный подграф с k вершинами. Алгоритм недетерминированно выбирает подмножество из k вершин и проверяет за время 0 ( №), является ли оно полным. Теперь мы должны доказать, что задача является о - труд-ной; мы сделаем это, показав, что в нее преобразуется задача выполнимости. [8]
Очевидно, из существования полиномиального алгоритма решения какой-нибудь NP-трудной задачи следует, что для каждой задачи из класса JT & ( для каждой ЛТ-полпой задачи в том числе) существует полиномиальный алгоритм ее решения. [9]
Трудоемкость означает, что неизвестны полиномиальные алгоритмы, решающие в общем случае эти задачи. [10]
Докажите, что существует недетерминированный полиномиальный алгоритм, отвечающий на вопрос является ли п составным. [11]
Докажите, что существует недетерминированный полиномиальный алгоритм, отвечающий на вопрос является ли п простым. [12]
В классической работе Л. Г. Хачияна предложен полиномиальный алгоритм для задачи линейного программирования с целыми коэффициентами, т.е. показано, что задачу линейного программирования можно решить на детерминированной машине Тьюринга за полиномиальное от длины входа L время. Под длиной входа подразумевается число символов 0 и 1, достаточное для записи в двоичной системе всех коэффициентов задачи. [13]
Следовательно, даже если есть полиномиальный алгоритм распознавания изоморфизма графов, с его помощью невозможно решить задачу изоморфного вложения за полиномиальное время. Она может быть решена за полиномиальное время, если GI - лес, a G2 - дерево. [14]
Дана аннотированная библиография работ по приближенным полиномиальным алгоритмам решения комбинаторных задач, для которых неизвестны точные полиномиальные алгоритмы. [15]