Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2 )M1, M2M1,M2M_1, M_2Л ( М1) ⊆...
Является ли следующая проблема в PTIME или coNP-hard: Даны два булевых выражения и в переменных без отрицания (т. Е. Выражения полностью построены с помощью и ). Решите, есть ли , то есть имеют ли они одинаковое значение для всех назначений переменных.е1е1e_1е2е2e_2Икс1, … ,...
Меня интересует сортировка массива положительных целочисленных значений за линейное время (в модели оперативной памяти с одинаковой мерой стоимости, т. Е. Целые числа могут иметь размер до логарифмического, но предполагается, что арифметические операции над ними будут выполняться единица времени)....
Для двух матриц A и B задача принятия решения о том, существует ли матрица перестановок P такая, что B = P - 1 A P , эквивалентна (граф изоморфизма). Но если мы расслабим P как просто обратимую матрицу, то в чем сложность? Существуют ли какие-либо другие ограничения на обратимую матрицу P , помимо...
Учитывая матрицу m×nm×nm \times n (при условии, что m≥nm≥nm \ge n ), каков самый быстрый алгоритм для вычисления его ранга и базиса столбцов? Я знаю, что это может быть решено с помощью линейного пересечения матроидов, что подразумевает детерминистический алгоритм времени...
Существует ли линейный алгоритм временного перемешивания на месте? Это алгоритм, который способны выполнить некоторые особенно ловкие руки: равномерно разделить входной массив четного размера, а затем чередовать элементы двух половинок. У Mathworld есть краткая страница о риффл-тасовке . В...
Рассмотрим # P-полную задачу подсчета числа покрытий вершин данного графа .G=(V,E)G=(V,E)G = (V, E) Я хотел бы знать, есть ли какой-либо результат, показывающий, как сложность такой проблемы изменяется с некоторым параметром (например, d = | E |GGG).d=|E||V|d=|E||V|d = \frac{|E|}{|V|} У меня такое...
Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) У меня есть...
Постоянное время - это абсолютный нижний предел сложности времени. Можно задаться вопросом: есть ли что-нибудь нетривиальное, что можно вычислить за постоянное время? Если мы придерживаемся модели машины Тьюринга, то мало что можно сделать, поскольку ответ может зависеть только от начального...
Я провел некоторый поиск по этому вопросу, но так или иначе не смог найти ответ. Гек ответил на это полностью. Благодарность
Известны ли результаты, которые исключают существование «слишком хороших, чтобы быть правдивыми» структур данных? Например: можно ли добавить функциональность и J o i n в структуру данных ведения заказа (см. Dietz and Sleator STOC '87 ) и при этом получить O ( 1 ) временных операций?Sp l i...
Хорошо известно, что сложность отличия монеты, смещенной на от монеты-монеты - это . Есть ли результаты для отличия монеты от монеты ? Я вижу, что для частного случая сложность будет . У меня есть догадка, что сложность будет зависеть от того, имеет ли порядок , но не может доказать это строго....
Мы говорим, что функция f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} является конструируемой во времени , если существует детерминированная многоленточная машина Тьюринга MMM которая на всех входах длины nnn делает не более f(n)f(n)f(n) шагов, и для каждого существует некоторый вход длина на которой...
Гауссовское исключение делает определитель матрицы полиномиальным временем вычислимым. Снижение сложности в вычислении детерминанта, которое в противном случае является суммой экспоненциальных членов, обусловлено наличием альтернативных отрицательных признаков (отсутствие которых делает вычисление...
Знаете ли вы о каких-либо проблемах (предпочтительно, по крайней мере, несколько хорошо известных), где для практического размера задачи экспоненциальный алгоритм работает намного быстрее, чем самый известный аналог полиномиального времени. Например, предположим, что задача имеет практический...
То, что я называю подсчетом, - это проблема, заключающаяся в том, чтобы найти количество решений для функции. Точнее, если задана функция f:N→{0,1}f:N→{0,1}f:N\to \{0,1\} (не обязательно черный ящик), приблизительный #{x∈N∣f(x)=1}=|f−1(1)|#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|,...
Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P...
Этот вопрос основан на существующем вопросе о том, можно ли моделировать стек с использованием двух очередей с амортизированным раз на операцию стека. Ответ кажется неизвестным. Вот более конкретный вопрос, соответствующий особому случаю, когда сначала выполняются все операции PUSH, а затем все...
Существуют ли разрешимые проблемы, такие, что для любого алгоритма, который решает проблему, мы можем дать ограничение по времени как функцию длины n входного экземпляра? Я пришел к этому вопросу, потому что думал о следующем: Предположим, у нас есть рекурсивно перечислимая, но неразрешимая...
Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .G = Zd1× Zd1… × ZdмG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}dяdid_i Производящая-набор { ч1, ... , чN}{h1,…,hn}\lbrace...