Арора и Барак показывают, что можно выразить как B P ⋅ N P, то есть набор языков, которые имеют рандомизированные сокращения до 3SAT. M A также является естественным рандомизированным обобщением N P в том смысле, что вы заменяете детерминированный верификатор на...
Допустим, мы обнаруживаем инопланетные цивилизации, которые могут отправлять и получать сообщения, используя межзвездный цифровой канал связи. (Скажем, с помощью модулированных радиоволн, лазерных импульсов, изменения положения звезд на различных орбитах.) Предположим, мы решили установить с ними...
Есть несколько конкурирующих понятий "разреженного графа". Например, встраиваемый в поверхность граф можно считать разреженным. Или график с ограниченной плотностью ребер. Или график с высоким обхватом. График с большим расширением. Граф с ограниченной шириной дерева. (Даже в подполе случайных...
Когда я думаю о программном обеспечении, которое небезопасно, я думаю, что оно «слишком полезно» и может быть использовано злоумышленником. Таким образом, обеспечение безопасности программного обеспечения - это процесс, который делает программное обеспечение менее полезным. В теоретической...
Учитывая , таким образом, что коэффициенты р , д ограничены B , имеет р ≡ Q удержание ?p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x1,…,xn),q(x1,…,xn)∈Z[x1,…,xn]p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]p,qp,qp,qBBBp≡qp≡qp\equiv q Здесь применима лемма Шварца-Циппеля, поскольку она...
Это продолжение моего предыдущего вопроса: Лучшая известная нижняя оценка сложности времени для естественной задачи в NP Я нахожу удивительным, что мы не смогли доказать какую-либо квадратичную детерминированную нижнюю границу для любой интересной проблемы NP, которая интересует людей и пытается...
Проводились ли какие-либо исследования, чтобы определить, может ли человеческий интеллект превзойти алгоритмы (т. Е. Проверить, применима ли теорема об отсутствии бесплатного обеда к человеческому интеллекту)? В том же ключе, кто-нибудь разработал технический метод, чтобы воспользоваться...
Чтобы ответить «какие проблемы можно решить с помощью вычислений», мы разработали теорию вычислимости. Для задач, которые являются вычислимыми, есть ли теория, чтобы ответить на вопрос «программа, которую я получаю, самая простая»? Я не думаю, что вычислительная сложность ответит на вопрос. Я...
Короче говоря, теоремы иерархии времени говорят о том, что машина Тьюринга может решить больше проблем, если у нее будет больше времени для вычислений. Подробно для детерминированных TM и функций, построенных по времени, с это и для недетерминированных функций TM и функций времени, f, g с f (n + 1)...
В сложности связи гипотеза лог-ранга утверждает, что с с ( М) = ( журналr k ( М) )O ( 1 )cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Где - сложность связи а - ранг (в виде матрицы) над реалами.M ( x , y ) r k ( M ) Mс с ( М)cc(M)cc(M)M( х , у)M(x,y)M(x,y)r k ( М)rk(M)rk(M)MMM Однако, когда вы...
В предыдущем вопросе об иерархии времени я узнал, что равенства между двумя классами можно распространять на более сложные классы, а неравенства можно распространять на менее сложные классы с аргументами, использующими заполнение. Поэтому возникает вопрос. Почему мы изучаем вопрос о различных типах...
Я давно интересовался различными темами, такими как комбинаторная логика, лямбда-исчисление, функциональное программирование, и изучал их. Однако, в отличие от «Теории вычислений», которая стремится ответить на вопрос «вычислимости», то есть вещей, которые могут / не могут быть вычислены с...
Недавно я подумал об «импорте» некоторых связанных с физикой вопросов в квантовую CS: Понятие явления закона площади в гамильтоновых системах обычно означает локальный гамильтониан на некоторой решетке, у основного состояния которого есть свойство, при котором запутывание любой замкнутой области...
Теория сложности вычислений классифицирует проблемы в соответствии с их сложностью. Теория сложных систем обращается к системам, которые демонстрируют поведение, которое, очевидно, не вытекает из свойств отдельных частей системы. Примеры включают хаотические системы, сложные адаптивные системы или...
Хорошо известно, что задача NP-Complete, называемая Subset Sum, имеет FPTAS. Мне было интересно, если существует проблема PSPACE Complete, которая также имеет FPTAS? Заранее
Этот пост отделен от Последствия UP равно NP , а также является дополнительным вопросом к классам семантической и синтаксической сложности . В вышеприведенном посте мы узнали о семантических и синтаксических классах. Вкратце, если класс можно охарактеризовать как листовой класс языка , то класс...
Я начал заниматься математической оптимизацией совсем недавно и мне это нравится. Кажется, многие проблемы оптимизации могут быть легко выражены и решены в виде линейных программ (например, сетевые потоки, покрытие краев / вершин, коммивояжёр и т. Д.). Я знаю, что некоторые из них являются...