Подсчет сложности МДП-решений задач с условими предшествования: полиномиально-разрешимые экземпляры и общий случай

Доклад продолжает серию о сокращении вычислительной сложности решения маршрутных задач по МДП под действием условий предшествования. Как оказалось, основной результат в этом направлении был получен Георгом Штейнером в 1990 году. Для МДП основным является ограничение на доступный объем памяти; фактически, это ограничение определяет целесообразность решения задачи методом динамического программирования, соответственно, вычисление этой характеристики имеет критическую важность. Как правило, для расчета пространственной сложности применяется аппарат идеалов частично упорядоченных множеств (зд. идеал — подмножество, в котором для произвольного его элемента, гарантированно содержатся все предшествующие ему); очевидно, эти идеалы полностью соответствуют "допустимым спискам заданий" в маршрутных задачах. В общем случае задача определения числа идеалов является #P-полной [Provan, Ball 1983]. В [Steiner 1990] описаны полиномиально-разрешимые варианты этой задачи, которые и составят основное содержание доклада. Также будет описан алгоритм, предложенный Штейнером для порождения всех идеалов за O(мощность ЧУМ) на каждый идеал и упомянут алгоритм Уайлда [Wild 2012], порождающий все идеалы заданной мощности за полином от их числа. Библиография: Provan J. S., Ball M. O. The complexity of counting cuts and of computing the probability that a graph is connected //SIAM Journal on Computing. – 1983. – Т. 12. – №. 4. – С. 777-788. Steiner G. On the complexity of dynamic programming for sequencing problems with precedence constraints //Annals of Operations Research. – 1990. – Т. 26. – №. 1. – С. 103-123. Wild M. Output-polynomial enumeration of all fixed-cardinality ideals of a poset, respectively all fixed-cardinality subtrees of a tree //Order. – 2012. – С. 1-15.