Нетривиальные задачи, решаемые за постоянное время?

Постоянное время - это абсолютный нижний предел сложности времени. Можно задаться вопросом: есть ли что-нибудь нетривиальное, что можно вычислить за постоянное время? Если мы придерживаемся модели машины Тьюринга, то мало что можно сделать, поскольку ответ может зависеть только от начального сегмента ввода постоянной длины, так как дальнейшие части ввода даже не могут быть достигнуты за постоянное время.

С другой стороны, если мы примем более мощную (и более реалистичную) модель ОЗУ с единичной стоимостью, в которой элементарные операции над числами -бит считаются за один шаг, то мы сможем решить нетривиальную задачу. задачи, даже в постоянное время. Вот пример: $O(\log n)$

Экземпляр: целые числа , каждый из которых задан в двоичном формате битами. $n, k, l, d$ $O(\log n)$

Вопрос: существует ли вершинный граф, такой, что его вершинная связность равна , его краевая связность равна , а его минимальная степень равна ? $n$ $k$ $l$ $d$

Обратите внимание, что из определения даже не очевидно, что проблема в NP . Причина в том, что естественный свидетель (график) может нуждаться в длинном описании -бит, в то время как ввод дается только битами. С другой стороны, на помощь приходит следующая теорема (см. Теория экстремальных графов Б. Боллобаса). $\Omega(n^2)$ $O(\log n)$

Теорема: Пусть целые числа. Существует вершинный граф с связностью вершин , связностью ребер и минимальной степенью , если и только если выполняется одно из следующих условий: $n, k, l, d$ $n$ $k$ $l$ $d$

, $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Поскольку эти условия можно проверять за постоянное время (в модели ОЗУ с единичной стоимостью), теорема приводит к алгоритму с постоянным временем в этой модели.

Вопрос: Каковы другие нетривиальные примеры алгоритмов с постоянным временем?

cc.complexity-theory ds.algorithms time-complexity Андрас Фараго
источник

Проверяет ли вероятностно проверяемое количество доказательств?

Дэвид Эппштейн

Не думайте, что ваш пример

раз. Ваш ввод имеет длину

, и в этом случае типичное слово RAM допускает операции

-бит только за один шаг. (Альтернатива состоит в том, чтобы разрешить размер слова, пропорциональный длине ввода, но в этом случае можно назвать много алгоритмов «постоянного времени» ...) Вы можете попытаться добавить строку длины

после этих чисел, но затем я не вижу, как проверка этого формата будет выполняться в

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ время: кажется, вы должны проверить (скажем, через бинарный поиск), что общая длина строки действительно

, что требует

времени.

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Райан Уильямс

Я думаю, что предложение Дэвида Эппштейна указывает на более интересное направление: рассмотрение рандомизированных O (1) -временных алгоритмов. По крайней мере, в этом случае вы можете надеяться, что каждый входной бит будет доступен как минимум за один возможный прогон алгоритма.

Райан Уильямс

Простым примером рандомизированных O (1) -временных алгоритмов является приблизительная медиана (приблизительная в том смысле, что она разделит входные данные примерно на 50-50). Просто случайным образом выберете 1000000 элементов из входных данных, рассчитайте их медиану и выведите их.

Юкка Суомела

Мне нравится ваш вопрос, но недостатком вашего примера является то, что он опирается на математическую теорему. Подойдя к этому пределу, вы можете сказать: Экземпляр Положительные целые числа

. Вопрос: существует ли целое число

такое, что

(ответ - True или False). Что ж, действительно существует алгоритм с постоянным временем, потому что ответ всегда ложный, но это явно не тот пример, который вам нужен.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

Ж.-Е.

Ответы:

В статье «Алгоритмы аппроксимации с постоянным временем с помощью локальных улучшений » Нгуена и Онака приведено много примеров схем случайного приближения с постоянным временем: максимальное совпадение (время выполнения зависит только от максимальной степени графа), задание покрытия и т. Д. Авторы представить метод для разработки таких алгоритмов.

Ламин
источник

Есть много примеров игр, изученных в теории комбинаторных игр, где состояние игры можно описать постоянным числом целочисленных значений. Для некоторых из них выигрышная стратегия для игры может быть рассчитана за постоянное время. Но они также поднимают вопросы о том, что именно ваша модель вычислений.

Одной из самых простых и основных комбинаторных игр является nim: в каждой есть постоянное количество куч бобов, и за один ход вы можете удалить любое количество бобов из одной колоды, будь то выигрыш или проигрыш (в зависимости от вашего выбора правил) если вы возьмете последний боб. Оптимальная стратегия может быть вычислена за постоянное время, если вы разрешите побитовые логические операции xor (т. Е. Оператор ^ в языках программирования, таких как C / C ++ / Java / и т. Д.). Является ли это алгоритмом с постоянным временем в вашей модели?

Вот тот, где известно, что существует точный детерминистический алгоритм с постоянным временем (в возможно нереалистичной расширенной модели вычислений, которая позволяет вам проверять простоту числа в постоянном времени), но неизвестно, что это за алгоритм: учитывая стартовый ход в игре монет Сильвер , определить, является ли это выигрышным или проигрышным ходом. Блок-схема для этой проблемы дана в Berlecamp, Conway и Guy, Winning Ways , но она зависит от конечного набора контрпримеров к общей характеристике выигрышных ходов, и неизвестно, что это за набор (или даже является ли он пустой).

Другой интересный пример из теории комбинаторных игр - игра Витоффа, Каждую игровую позицию можно описать парой целых чисел (т. Е. Постоянным пробелом в вашей модели вычислений), ходы в игре предполагают уменьшение одного из этих двух целых чисел до меньшего значения, а стратегия выигрыша предполагает переход в позицию, в которой соотношение между этими двумя целыми числами максимально приближено к золотому. Но во многих игровых позициях есть выбор: вы можете уменьшить большее из двух целых чисел либо до точки, где оно будет (почти) меньше, чем целое число, умноженное на золотое сечение, либо на меньшее целое число, деленное на золотое сечение. Только один из этих двух вариантов будет выигрышным ходом. Таким образом, оптимальная стратегия может быть определена в терминах постоянного числа арифметических операций, но эти операции включают иррациональное число, золотое сечение. Это алгоритм с постоянным временем в вашей модели? Возможно это' (приближение к золотому сечению с точностью до $n$ $\log n$ битов), но не постоянное время с использованием только арифметических операций (без квадратных корней) и фиксированных значений целочисленных констант?

Дэвид Эппштейн
источник

Спасибо, это все интересные примеры. Они также хорошо проливают свет на тот факт, что концепция «постоянного времени» менее ясна, чем я первоначально думал ...

Андрас Фараго

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
источник