Положительный топологический порядок, дубль 2

12

Это продолжение недавнего вопроса Дэвида Эппштейна и мотивировано теми же проблемами.

Предположим, у меня есть вершина с весами действительных чисел на его вершинах. Первоначально все вершины не отмечены. Я могу изменить набор отмеченных вершин, либо (1) помечая вершину без неотмеченных предшественников, либо (2) снимая пометку с вершины без отмеченных преемников. (Таким образом, набор отмеченных вершин всегда является префиксом частичного порядка.) Я хочу найти последовательность операций маркировки / снятия пометок, которая заканчивается всеми отмеченными вершинами, так что общий вес отмеченных вершин всегда неотрицателен ,

  • Насколько сложно найти такую ​​последовательность операций? В отличие от проблемы Дэвида , даже не ясно, что эта проблема в NP; в принципе (хотя у меня нет примеров) каждая легальная последовательность шагов может иметь экспоненциальную длину. Лучшее, что я могу доказать, это то, что проблема в PSPACE.

  • Является ли операция снятия отметки ненужной? Если существует допустимая последовательность перемещений, должна ли быть допустимая последовательность перемещений, которая никогда не помечает вершину? Положительный ответ сделал бы эту проблему , идентичную с Давидом . С другой стороны, если снятие отметки иногда необходимо, должен быть небольшой пример (постоянный размер), который доказывает это.

Jeffε
источник
1
Эта статья показывает, что проблема, связанная со
свободными отношениями, сложна для
Похоже на игру в гальку: en.wikipedia.org/wiki/Pebble_game .
Уоррен Шуди
Недавно опубликованная статья: cs.utoronto.ca/~philipp/pages/papers/BWPebbling.pdf . Игра с черной галькой похожа на вашу, но отличается тем, что промежуточные узлы можно не отметить, даже если преемник отмечен.
Уоррен Шуди

Ответы:

5

На нашем обычном 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 положителен.

domotorp
источник
1
Ваши определения Y-вверх и Y-вниз идентичны. Предположительно, подмножество X Y является Y-down, если каждый элемент Y, который меньше, чем элемент X, также находится в X.
Джефф
1
Очень круто! Ответ может быть более понятным, если в первой строке указано, какое утверждение вы доказываете. Я так понимаю, это доказательство того, что разметка никогда не нужна (если вы можете решить ее с помощью разметки, вы можете найти последовательность, которая также решает ее, не помечая ничего)? (И не, например, доказательство того, что эта проблема является NP-трудной / PSPACE-трудной, или алгоритма полиномиального времени, который может решить, существует ли такая последовательность разметки (или найти ее).) Кроме того, позже в описании, где он говорит «в любой момент», мне не ясно, означает ли это «во всех точках» или «в какой-то момент»; Я подозреваю, что вы имеете в виду первое?
DW