Вопросы с тегом «cc.complexity-theory»

18
Почему P = NP не подразумевает P = AP (то есть P = PSPACE)?

Хорошо известно, что если то иерархия полиномов разрушается и .P = N PP=NP\mathbf{P}=\mathbf{NP}P = P HP=PH\mathbf{P}=\mathbf{PH} Это можно легко понять индуктивно с помощью оракулов. Вопрос в том, почему мы не можем продолжить индуктивный процесс за пределами постоянного уровня чередований и...

18
Прямое снижение SAT до 3-SAT

Здесь цель состоит в том, чтобы свести произвольную задачу SAT к 3-SAT за полиномиальное время, используя наименьшее количество предложений и переменных. Мой вопрос мотивирован любопытством. Менее формально я хотел бы знать: «Каково« наиболее естественное »сокращение с SAT до 3-SAT?» Теперь...

18
Может ли тестирование показать отсутствие ошибок?

(n+1)(n+1)(n + 1) точек необходимы для однозначного определения многочлена степени ; например, две точки на плоскости определяют ровно одну линию.nnn Сколько точек требуется для однозначного определения вычислимой функции , учитывая длину программы, которая вычисляет на фиксированном языке? (т.е....

18
Компромисс между временем и сложностью запроса

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

18
Самый эффективный способ преобразовать цепь

РЕДАКТИРОВАТЬ (22 августа 2011 г.): Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу...

18
Использование XORification

XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...

18
Модели вычислений строго между классическими и квантовыми с точки зрения сложности запросов

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

18
Точное решение суперструны

Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем O∗(2n)O∗(2n)O^*(2^n) ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP? UPD: подавляет полиномиальные факторы.O∗(⋅)O∗(⋅)O^*(\cdot) Самая короткая...

18
Список теорем о том, что P не равен NP тогда и только тогда, когда

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

18
Кратчайший эквивалент формулы CNF

Пусть F1F1F_1 - выполнимая формула CNF с nnn переменными и mmm предложениями. Пусть SF1SF1S_{F_1} - пространство решений F1F1F_1 . Рассмотрим проблему определения для данной F1F1F_1 другой формулы CNF F2F2F_2с тем же набором переменных, что и для F1F1F_1 , с SF2=SF1SF2=SF1S_{F_2} = S_{F_1} (то же...

18
Какова «реальная» причина того, что IP = PSPACE является нерелятивизирующим?

ООOC ø N P O ⊆ P S P C E O Oc o N PОP я PОсоNпО⊈япО{\sf coNP}^O \not\subseteq {\sf IP}^Oc o N PО⊆ Р С Р С ЕОсоNпО⊆пSпAСЕО{\sf coNP}^O \subseteq {\sf PSPACE}^OООO Тем не менее, я видел только несколько человек, которые дают «прямое» объяснение того, почему результат не релятивизируется, и обычный...

18
Какова сложность подсчета случайных 2-SAT?

Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны...

18
Почему мы используем одиночные ленточные машины Тьюринга для сложности времени?

Как вы знаете, существует много аномалий для одиночных ленточных машин Тьюринга, когда время : симуляция ТМ с несколькими лентами, симуляция большого алфавита ленты с просто { 0 , 1 , b } , возможность построения времени, неплотность теоремы иерархии времени,...

18
Ищите хорошую проблему внутри СЦ, но не на первых двух уровнях

Сложность зоопарк не имеет много о SCSC\mathsf{SC} . Я ищу хорошую † проблему, которая находится на более высоких уровнях иерархии, то есть проблему в D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n ), но о которой неизвестно в D Т я м ē S р с е ( п O ( 1...

18
Насколько тяжела мафия?

Мафия - популярная ролевая игра на вечеринках, подробное описание доступно на википедии http://en.wikipedia.org/wiki/Mafia_%28game%29 . В основном это работает следующим образом: В начале каждому из игроков тайно отводится роль, связанная либо с мафией, либо с городом. Каждая роль может иметь...

18
Случайность покупает нам что-нибудь внутри P?

Пусть будет классом решений задач, имеющих рандомизированный алгоритм с ограниченной двусторонней ошибкой, работающий за время .O ( f ( n ) )BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n))O(f(n))O(f(n))O(f(n)) ли нам какие-либо проблемы такие, что но ? Доказано ли его несуществование? Q ∈ B P T I M E...

18
Есть ли теория, которая сочетает в себе теорию категорий / абстрактную алгебру и вычислительную сложность?

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

18
Все ли функции, вес Фурье которых сконцентрирован на множествах малого размера, вычисляются цепями AC0?

Все ли функции, чей вес Фурье сконцентрирован на множествах малого размера (или членах с низкой степенью), вычисляются по схемам

18
Мотивация использования карп-редукций в теории

Понятие полиномиального сокращения времени (сокращения Кука) является абстракцией очень интуитивного понятия: эффективное решение проблемы с использованием алгоритма для другой задачи. Тем не менее, в теории -полнота, понятие N P -hardness захватывается с помощью сокращений (сокращения отображения...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...