Это продолжение недавнего вопроса Дэвида Эппштейна и мотивировано теми же проблемами.
Предположим, у меня есть вершина с весами действительных чисел на его вершинах. Первоначально все вершины не отмечены. Я могу изменить набор отмеченных вершин, либо (1) помечая вершину без неотмеченных предшественников, либо (2) снимая пометку с вершины без отмеченных преемников. (Таким образом, набор отмеченных вершин всегда является префиксом частичного порядка.) Я хочу найти последовательность операций маркировки / снятия пометок, которая заканчивается всеми отмеченными вершинами, так что общий вес отмеченных вершин всегда неотрицателен ,
Насколько сложно найти такую последовательность операций? В отличие от проблемы Дэвида , даже не ясно, что эта проблема в NP; в принципе (хотя у меня нет примеров) каждая легальная последовательность шагов может иметь экспоненциальную длину. Лучшее, что я могу доказать, это то, что проблема в PSPACE.
Является ли операция снятия отметки ненужной? Если существует допустимая последовательность перемещений, должна ли быть допустимая последовательность перемещений, которая никогда не помечает вершину? Положительный ответ сделал бы эту проблему , идентичную с Давидом . С другой стороны, если снятие отметки иногда необходимо, должен быть небольшой пример (постоянный размер), который доказывает это.
Ответы:
На нашем обычном 666 исследовательском семинаре мы нашли следующее доказательство.
Начнем с некоторых определений. Позвольте P быть нашим poset. Для простоты предположим, что ни один из весов не суммирует до нуля. Обозначим вес вершины через w (x), а сумму весов множества через w (X). Мы говорим, что множество X является Y-вверх (замкнутым), если оно содержится в Y, и каждый элемент Y, который больше, чем элемент X, также находится в X. Аналогично, скажем, что множество X является Y-вниз, если оно содержится в Y, и каждый элемент Y, который меньше, чем элемент X, также находится в X. На этом языке набор отмеченных элементов должен быть всегда P-down.
Докажем противоречием. Возьмите самую короткую последовательность отметки / снятия отметки, которая помечает каждый элемент. Мы называем такие последовательности полными. В любой данный момент рассмотрим набор элементов, которые были отмечены ранее, но теперь не отмечены. Обозначим это множество как U.
Утверждение: w (U)> 0.
Доказательство. Докажем, что вес любого множества U-up X положителен. Доказательством служит индукция по размеру X. Если существует множество X-вниз Y, такое, что w (Y)> 0, то по индукции мы знаем, что w (X \ Y)> 0 (так как оно X-up), мы также имеем w (X)> 0. Если для каждого множества X-down Y мы имеем w (Y) <0, то, удалив до этого момента все маркировки и немаркировки элементов X из нашей последовательности, мы получим более короткую полную последовательность. Мы сделали с доказательством претензии.
Теперь предположим, что у нас есть полная последовательность, где w (U)> 0 в любой точке для множества U в настоящее время неотмеченных элементов. Возьмем последовательность, которую мы получаем из этого, взяв первую маркировку каждого элемента и никогда ничего не отмечая. Ясно, что это также будет полная последовательность, удовлетворяющая, что набор отмеченных элементов всегда P-down. Более того, сумма весов всегда будет, по крайней мере, такой же, как в исходной последовательности, поскольку в любой момент времени разница равна w (U). Мы сделали.
С помощью этого метода можно даже доказать, что если вместо разметки всего P мы хотим пометить только подмножество P, то это можно сделать с помощью последовательности разметок, за которой следует последовательность разметок. Доказательство то же самое, за исключением того, что в конце некоторые элементы, U, остаются неотмеченными, но их можно переместить в конец последовательности, поскольку вес любого набора U-up положителен.
источник