Как доказать, что проблема неразрешима при определенной временной сложности?
Обсуждая локальный минимум в матричной проблеме n x n с моим профессором, он предположил, что для этой задачи существует решение с O(log n) временной сложностью. Теперь я почти уверен, что он неправ, хотя и не уверен, как доказать отсутствие такого алгоритма. Я был бы признателен за любые идеи или методологии, которые можно использовать, чтобы продемонстрировать невозможность решения этой конкретной проблемы за O(log n) время.
Кроме того, это приводит меня к более общему вопросу:
Как можно доказать, что задачу невозможно решить за заданное время?
Спасибо!
@user24714692 user24714692 не отсортировано, значения в матрице распределены случайным образом.
«Как можно доказать, что проблему невозможно решить за заданную временную сложность?» Когда вы решите эту задачу, не забудьте отметить в своем календаре: вам нужно будет получить премию Тьюринга, медаль Филдса и чек на миллион долларов от института Клея. Ненавижу, когда пропускаю такие встречи.
@n.m.couldbeanAI, честно говоря, он, вероятно, имеет в виду эту конкретную проблему или пример подобной проблемы.
Я бы сказал, что обязанность профессора – подкреплять свои утверждения. но в любом случае, хотя я и не эксперт в теории сложности, вы должны быть в состоянии доказать, что он/она не прав, показав конкретный пример задачи, в которой сложность увеличивается как N. например, что, если все элементы равны, кроме одного. Тем не менее, я рекомендую вам уточнить, что именно он/она подразумевает под сложностью O, это худший случай, средний случай? скорее всего, вы обнаружите, что он/она говорил о немного другой проблеме или немного другом значении слова «худший случай».
@n.m.couldbeanAI Я могу доказать, что сортировка на основе сравнения не может иметь худшего случая, то есть o( log(n)). Как мне получить свой приз?
Я почти уверен, что вы можете использовать состязательный метод, чтобы доказать, что решение этой проблемы требует времени O(n). Посмотрим, смогу ли я что-нибудь придумать, но технику смотрите youtube.com/watch?v=3F3EKJNGNSQ
@btilly Ты забыл решить все остальные проблемы.
@n.m.couldbeanAI И вы забыли, что, несмотря на заголовок, ФП хотел решить только один вопрос. Иногда это ответный вопрос.
@btilly Не только. «Кроме того, это подводит меня к более общему вопросу».
@n.m.couldbeanAI Я воспринял это как вопрос о том, как это возможно в принципе. Что весьма отличается от того, всегда ли это возможно.
@btilly Я не понимаю, как наличие доказательства для конкретного случая или сотни может ответить на вопрос в целом. Общий вопрос требует общего ответа. В противном случае вопрос был бы совершенно излишним, поскольку выше стоит еще один вопрос о доказательстве в конкретном случае.
Ответы 1
Имея алгоритм, который решает проблему локального минимума, мы можем написать состязательный алгоритм, который наблюдает за его работой и определяет значение каждой ячейки матрицы непосредственно перед тем, как на нее смотрит решатель.
Поскольку назначения, которые делает противник, представляют собой действительные входные данные, которые могли быть предоставлены решателю вначале, если противник всегда может заставить решатель проверить более Ω(log n) ячеек, прежде чем он сможет доказать локальный минимум, тогда это доказывает, что в худшем случае поиск локального минимума должен занять время, превышающее Ω(log n).
Учитывая, что решатель не может доказать локальный минимум, пока каждая проверенная им ячейка имеет меньшего или неисследованного соседа, такой противник может действовать следующим образом.
Непосредственно перед тем, как решатель исследует ячейку, которой еще не присвоено значение (неназначенная ячейка):
- Если новое назначение разделит непрерывную область неназначенных ячеек на 2 или более частей, то выбирается наибольшая из этих частей, которая останется неназначенной. Остальные части, вместе с новой ячейкой, заполняются значениями, которые ниже всех использованных до сих пор значений, причем значения увеличиваются по мере увеличения их расстояния от новой ячейки, так что только новая ячейка может стать локальным минимумом. Обратите внимание, что он останется с неназначенным соседом в выбранном регионе, поэтому это не доказуемый минимум.
- В противном случае новая ячейка не разделяет область неназначенных ячеек — она находится либо на границе такой области, либо на острове посередине. Ему присваивается значение, меньшее, чем все ранее использованные значения. Это может привести к доказуемому минимуму только в том случае, если ячейка полностью окружена назначенными ячейками.
Обратите внимание, что согласно условию (1) противник всегда сохраняет инвариант, согласно которому все неназначенные ячейки соединены.
Чтобы доказать минимум, решатель должен действовать до тех пор, пока эта область связанных ячеек не достигнет размера 1, и решатель не заполнит ее.
Но затем, если мы рассмотрим связанные области ячеек, которые не исследовал решатель, мы увидим, что каждая такая область должна быть частью одной из связанных областей, которая не была выбрана противником в условии (1), потому что это единственные клетки, которые не были исследованы.
Поскольку противник всегда выбирает самый большой регион для обслуживания, каждый невыбранный регион имеет размер < n2/2.
Если мы заполним ячейки, проверенные решателем, то он оставит незаполненными только области размером < n2/2 в полной матрице из n2 ячеек. Поскольку для этого вам нужно заполнить как минимум n ячеек (оптимальный способ — просто провести линию посередине), решатель должен изучить как минимум n ячеек и не сможет доказать минимум менее чем в Ω. (н) время.
Найти локальный минимум в отсортированной или несортированной матрице
n x n?