Любая алгоритмическая задача имеет сложность времени, в которой преобладает счет?

То, что я называю подсчетом, - это проблема, заключающаяся в том, чтобы найти количество решений для функции. Точнее, если задана функция $f:N\to \{0,1\}$ (не обязательно черный ящик), приблизительный $\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$,

Я ищу алгоритмические проблемы, которые включают какой-то счет и для которых сложность времени сильно зависит от этой основной проблемы счета.

Конечно, я ищу проблемы, не считая проблем сами. И было бы очень полезно, если бы вы могли предоставить документацию по этим проблемам.

Это продолжение ответа Суреша. По его словам, в вычислительной геометрии существует множество проблем построения, в которых сложность вывода является тривиальной нижней границей времени выполнения любого алгоритма. Например: расположение планарных линий, трехмерные диаграммы Вороного и графы плоской видимости имеют комбинаторную сложность в худшем случае, поэтому любой алгоритм, который строит эти объекты, тривиально требует Ω ( n 2$\Theta(n^2)$$\Omega(n^2)$ в худшем случае , (Существуют -временные алгоритмы для всех трех из этих проблем.)$O(n^2)$

Но подобные ограничения предполагаются также для решения проблем. Например, учитывая набор из n линий на плоскости, как легко вы можете проверить, проходят ли какие-либо три линии через общую точку? Ну, вы можете построить расположение линий (планарный график, определенный их точками пересечения и отрезками между ними), но это займет времени. Одним из основных результатов моей кандидатской диссертации было то, что в рамках ограниченной, но естественной модели вычисления дерева решений, Ω ( n 2$\Theta(n^2)$ требуется$\Omega(n^2)$для обнаружения тройных пересечений. Интуитивнонадовсе перечислить точки пересечения и поиск дубликатов.$\binom{n}{2}$

Аналогично, существует набор чисел, где троек элементов суммируются с нулем. Таким образом, любой алгоритм (моделируются некоторым классом дерев решений) , чтобы проверить данный набор содержит ли три элемента, сумма к нулю требует Ома ( п 2 ) времени . ( Некоторые журналы можно сбрить с помощью параллелизма на уровне битов, но неважно.)$\Theta(n^2)$$\Omega(n^2)$

Другим примером, также из моего тезиса, является проблема Хопкрофта: учитывая точек и n линий на плоскости, содержит ли любая точка какую-либо линию. Худший случай количество точечных линий числа случаев , как известно, Θ ( п 4 / 3 ) . Я доказал , что в модели ограничен (но по- прежнему естественным) вычисления, П ( п 4 / 3 ) требуется время , чтобы определить , есть ли еще одна точка линии падения. Наглядно, мы должны перечислить все thetas ; ( п 4 / 3 ) вблизи$n$$n$$\Theta(n^{4/3})$$\Omega(n^{4/3})$$\Theta(n^{4/3})$ -посмотреть и проверить каждый из них, чтобы увидеть, действительно ли это заболевание.

Формально эти нижние оценки все еще являются лишь предположениями, потому что они требуют ограниченных моделей вычислений, которые специализируются на рассматриваемой проблеме, особенно для проблемы Хопкрофта). Однако, доказательство нижних границ для этих проблем в модели RAM, вероятно, так же сложно, как и любая другая проблема с нижними границами (т. Е. Мы понятия не имеем) - см. Статью Патраску и Уильямса SODA 2010, в которой обобщения 3SUM соотносятся с экспоненциальным временем. гипотеза.

$|V|^{2.376}$ в 1978 году. Точно так же лучший способ, который мы знаем для обнаружения k-клики, - это найти число k -клики, опять же с помощью умножения матриц.

Валиант доказал, что проблема нахождения перманента матрицы завершена для #P . Смотрите страницу википедии по этому вопросу. #P - класс сложности, соответствующий подсчету количества принимающих путей машины NP.

Двухстороннее плоское (и логарифмическое родство) Perfect Matching - проблема, в которой алгоритм Кастеллина для подсчета плоских совпадений (расширенный Galluccio и Loebl и распараллеленный Kulkarni, Mahajan & Vardarajan) играет важную роль даже в поисковой версии проблемы. Все соответствующие ссылки можно найти в следующей статье:

Некоторые идеальные соответствия и идеальные полуцелые соответствия в NC. Рагхав Кулкарни, Мина Махаджан и Кастури Р. Варадараджан. Чикагский журнал теоретической информатики, том 2008, статья 4.

Я восприму «большое влияние» как мягкое ограничение, а не как сокращение. В этом смысле МНОГИЕ задачи в вычислительной геометрии имеют время выполнения, ограниченное некоторой комбинаторной структурой, лежащей в их основе. например, сложность вычисления схемы форм напрямую связана с внутренней сложностью таких схем.

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

Не уверен, что это именно то, что вы искали, но фазовые переходы задач NP-Complete сильно зависят от вероятностных аргументов, которые являются еще одной формой подсчета.

LLL использовался для решения некоторых задач «Подмножества сумм с низкой плотностью», успех которых зависит от существующих с высокой вероятностью коротких векторов решетки, которые соответствуют критериям того, чтобы быть решением Подмножества сумм. Распространение результатов опроса зависит от структуры пространства решений (и количества решений, фиксирующих переменные) для поиска решений вблизи критического порога.

Borgs, Chayes и Pittel в значительной степени полностью охарактеризовали фазовый переход (равномерной) проблемы разбиения случайных чисел и, таким образом, охарактеризовали, сколько решений можно ожидать для данного (случайного) экземпляра проблемы разбиения чисел.