Существуют ли разрешимые задачи, для которых без алгоритма мы можем дать временные ограничения?

Существуют ли разрешимые проблемы, такие, что для любого алгоритма, который решает проблему, мы можем дать ограничение по времени как функцию длины n входного экземпляра?

Я пришел к этому вопросу, потому что думал о следующем:

Предположим, у нас есть рекурсивно перечислимая, но неразрешимая проблема. Предположим далее, что я - "да" -инстанция проблемы. Тогда для любого алгоритма, который бы идентифицировал "да" -экземпляры проблемы, мы можем дать временную границу в терминах размера n из I. Поскольку, если бы мы могли дать такую ​​временную границу, мы могли бы решить проблему, так как мы могли бы просто сделать вывод, что я являюсь экземпляром "нет", когда превышен срок.

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

Для каждого алгоритма который оканчивается на классе входных данных , мы можем определить функцию его времени выполнения: где - класс входов длины а - алгоритм времени, который требуется для завершения на , Конечно, это определение является неудовлетворительным, поскольку оно относится к алгоритму, но оно показывает существование такой функции. Вопрос, который остается, состоит в том, существует ли краткое представление (и я считаю, что это было то, что вы просили).$A$$\mathsf{In}$I n ( n ) n t i m e ( A ( i ) ) A

Если мы используем простые алгебраические термины (без какой-либо рекурсии) в качестве определения краткого, то я думаю, что ответ будет отрицательным: есть проблемы, которые можно решить, но сложность которых не является элементарной. То есть не существует стека вида который ограничивает время выполнения алгоритма для задачи размера n.$2^{2^{2^{2^{\dots^n}}}}$

Надеюсь, я правильно понял ваш вопрос.

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

Иногда можно доказать, что проблема разрешима, не имея возможности показать алгоритм для нее. Самым известным примером такого рода вещей является работа Робертсона и Сеймура над младшими графами, которая показывает, что любое свойство наследственного графа может быть определено за полиномиальное время, проверяя наличие подходящего конечного списка запрещенных миноров. Их доказательство показывает только то, что существует конечный список запрещенных несовершеннолетних, но не дает рецепта для поиска списка.

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

Еще одно замечание: поскольку мы знаем, что проверка несовершеннолетнего может быть выполнена за времени, вы можете утверждать, что во всех случаях, представленных алгоритмом Робертсона – Сеймура, у нас действительно есть «граница» на время выполнения. Тем не менее, я бы сказал, что это обман, если мы не ограничены константой.O ( n 3$O(n^3)$$O(n^3)$

Просто чтобы добавить другую точку зрения, позвольте мне напомнить, что не каждая проблема имеет «внутреннюю» сложность, что, вероятно, является наиболее интересным и каким-то образом пренебрежимым следствием теоремы Блюма об ускорении.

По существу, теорема утверждает, что при фиксированном желаемом ускорении g вы всегда можете найти вычислительную задачу P, такую, что для любой программы, решающей P, существует другая программа, все еще решающая P и выполняющая g-раз быстрее, чем предыдущая.

Следовательно, для такого рода проблем вы не можете дать ограничение по времени. Удивительный и довольно удивительный результат. Конечно, P имеет очень большую сложность.

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

Ответ - да: например, может случиться так, что у вас есть полуалгоритм для случаев ДА вашей проблемы и полуалгоритм для НЕТ экземпляров. Это дает вам возможность решить вашу проблему, но без ограничений по времени.

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

Затем у вас есть следующий алгоритм, чтобы решить, является ли тождество истинным: перечислите параллельные доказательства и конечные структуры и остановитесь, когда найдете доказательство или структуры, свидетельствующей о том, что ложно. Это дает вам правильный алгоритм , но никакой сложности не связаны, если не может ограничивать размер доказательств и конечных структур по отношению к .я я $I$$I$$I$$I$

Примером этого является аффинная линейная логика (LLW): в настоящее время известно, что она завершена в башне [1], но в течение некоторого времени не было известно никаких границ, и была показана только разрешимость, используя среди прочих методов свойство конечной модели [2] ,

Ссылки:

[1] Неэлементарные сложности для ветвления VASS, MELL и расширений. Ранко Лазич и Сильвен Шмитц. CSL-LICS 2014

[2] Свойство конечной модели для различных фрагментов линейной логики. Ив Лафонт, J. Symb. Логика. 1997

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

1) в теоремах о пространственно-временной иерархии требуется понятие «конструируемых во времени» и «конструируемых во времени» функций. Существуют не конструируемые во времени и не пространственно восстанавливаемые функции, которые приводят к необычным свойствам, обнаруживаемым в теоремах Блюма, таких как теоремы «разрыв, ускорение». большинство (все?) классы сложности std определены в терминах пространственно-временных функций.

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

3) в теории арифметики существуют неисчислимые последовательности чисел в теории чисел, которые можно интерпретировать как создание временных границ, не поддающихся вычислению в смысле, таких как последовательность Гудстейна или теории Париса - Харрингтона.