Класс UP определяется так: Класс решения задач, решаемых машиной NP, такой, что Если ответ «да», принимается ровно один путь вычислений. Если ответ «нет», все пути вычислений отклоняются. Я пытаюсь развить интуицию для этого определения. Можно ли сказать, что проблемы UP - это проблемы с...
«Вторая » проблема - это проблема принятия решения о существовании другого решения, отличного от некоторого данного решения для экземпляра проблемы.XXX Для некоторых задач с завершением второй версией решения является -complete (решающий вопрос о существовании другого решения для задачи с частичным...
Impagliazzo, Paturi и Calabro, Impagliazzo, Paturi представили гипотезу экспоненциального времени (ETH) и гипотезу сильно экспоненциального времени (SETH). Грубо говоря, SETH говорит, что нет алгоритма, который решает SAT за время . 1.99n1.99n1.99^n Мне было интересно, что бы это значило, чтобы...
Существует ли 2DFA с состояниями (где n нетривиально, скажем, по крайней мере 4), для которых требуется по крайней мере 2 n состояния для моделирования с использованием любого DFA?NnnNnn2N2n2^n Двусторонний DFA (2DFA) является детерминированным конечным числом состояний автомата , который может...
Я ищу класс сложности, который относится к APX, так как BPP относится к P. Я уже задавал этот же вопрос здесь , но, возможно, TCS будет более плодотворным местом для ответов. Причина этого вопроса заключается в том, что в практических задачах часто приходится находить приблизительные ответы...
Знаете ли вы задачи, которые являются W [1] -твердыми даже для ограниченных графов степеней? Метрическое измерение сложно на графах со степенью не более 3, но это W [2] -твердый. Красно-синий неблокатор был W [1] -твердым на ограниченных графах степеней, но в доказательстве была ошибка (книга...
Есть ли документированный способ вычисления узлов? (окружности, вложенные в трехмерное евклидово пространство). Я имею в виду тип данных для их представления и алгоритм для определения, представляют ли два экземпляра типа один и тот же узел. Если ответ положительный, как насчет сложности этой...
Известно ли следующее утверждение? Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( √граммGGNnnграммGGO (...
У меня есть вопрос относительно чистых функций. Согласно странице Википедии, один из необходимых компонентов для чистой функции: Оценка результата не вызывает какого-либо семантически наблюдаемого побочного эффекта или вывода, такого как мутация изменяемых объектов или вывод на устройства...
Насколько я знаю, нижняя граница нормы факторизации, данная Линиалом и Шрайбманом, является по существу единственной нижней границей, известной для сложности квантовой связи (или, по крайней мере, она включает все остальные). Есть ли доказательства того, что эта граница была жесткой? Граница...
В теоремах бесплатно! Вадлер говорит, что характеристика параметричности может быть выражена в терминах слабых естественных преобразований, и это будет предметом дальнейшей статьи. На какую бумагу он ссылается? Я знаю, что категорический подход к параметричности использует динатуральные...
После прочтения соответствующего вопроса о неконструктивных доказательствах существования алгоритмов мне стало интересно, есть ли способы показать существование «маленьких» (скажем, состояний) вычислительных машин без фактического их построения. Формально: предположим, нам дан некоторый язык и...
Теория типов Мартина-Лёфа использует W-типы для определения индуктивных структур, таких как целые числа, списки и т. Д. Однако, исчисление индуктивных конструкций не использует их одинаково, индуктивные типы там больше похожи на схемы аксиом. Являются ли эти два подхода эквивалентными (они...
Обозначим через минимальную степень выхода в G , а через δ - ( G ) минимальную степень.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) В связанном вопросе я упомянул расширение Гуила-Хури теоремы Дирака о гамильтоновых циклах , которое предполагает, что если тогда G...
Таким образом, проблема покрытия множеств является тривиальной, если ни один из наборов кандидатов не пересекается друг с другом. Однако что, если размер пересечения для любой пары наборов кандидатов был не больше 1? Эта проблема NP-сложная? Я был бы признателен за любое понимание. Спасибо...
Вот проблема с похожим вкусом к изучению хунт: Входные данные: функция f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , представленная оракулом членства, то есть оракулом, который дал xxx , возвращает f(x)f(x)f(x) . Цель: Найти вложенный куб SSS из {0,1}n{0,1}n\{0,1\}^n с объемом...
Как упомянул @Marzio, следующая игра называется Generalized Geography . Для графа и начальной вершины игра определяется следующим образом:G = ( V, E)гзнак равно(В,Е)G=(V,E)v ∈ Vv∈Вv \in V На каждом ходу (чередуются два игрока), игрок выбирает , и тогда происходит следующее:u ∈ N( v )U∈N(v)u\in N(v)...
Стандартное доказательство того, что BQPSPACE находится в PSPACE, основано на анализе типа игры Савича на интегралах пути. Однако предполагается, что длительность BQPSPACE не должна превышать экспоненциально большую длину. Это верно для PSPACE, но для замкнутых квантовых систем с фиксированным...
Я пытаюсь понять, что связано с теоретическими компьютерными исследованиями. Что делают теоретические компьютерные ученые? Я знаю, что значительное время затрачивается на преподавание, руководство аспирантами, подачу заявок на финансирование и выполнение обязанностей департамента. Отложив их в...
Кросспост из МО . Пусть - класс графов, определенный конечным числом запрещенных индуцированных подграфов, причем все они циклические (содержат хотя бы один цикл).СCC Существуют ли NP-сложные графовые задачи, которые можно решить за полиномиальное время для кроме Clique и Clique cover?СCC Если я...