Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...
(Извините, если это хорошо известно.) Я хотел бы передать какой-то предмет одному из агентов, чтобы агент получил предмет с вероятностью . Существует ли криптографический (или другой) инструмент, позволяющий каждому агенту (и даже каждому наблюдателю) быть уверенным в том, что случайное рисование...
Предположим, что граф с раскрасочным числом . Рассмотрим следующую игру между Алисой и Бобом. В каждом раунде Алиса выбирает вершину, и Боб отвечает цветом для этой вершины. Игра заканчивается, когда монохроматический край обнаружен. Пусть будет максимальной продолжительностью игры при оптимальной...
Я хотел бы спросить о частном случае вопроса « Решение, вычисляет ли данная схема NC 0 перестановку » QiCheng, который остался без ответа. Булева схема называется цепью NC 0 k , если синтаксически каждый выходной вентиль зависит не более чем от k входных вентилей. (Мы говорим, что выходной вентиль...
В вычислительной сложности есть важное различие между монотонными и общими вычислениями, и знаменитая теорема Разборова утверждает, что 3-SAT и даже MATCHING не являются полиномами в модели монотонных булевых схем. Мой вопрос прост: есть ли квантовый аналог для монотонных цепей (или нескольких)?...
Изменить: я выбираю ответ с наибольшим количеством баллов до 6 декабря 2012 года. Это мягкий вопрос. Концепция (детерминированных) алгоритмов восходит к BC. Как насчет вероятностных алгоритмов? В этой статье в вики в качестве первого рандомизированного алгоритма (год ???) был задан алгоритм Рабина...
Изучение экологии и эволюции становится все более математическим, но большинство теоретических инструментов, похоже, исходит от физики. Однако во многих случаях проблемы носят весьма дискретный характер (см., Например, SLBS00 ) и могут быть полезны с точки зрения информатики . Тем не менее, я знаю...
Недавно я читал «Две дуальности вычислений: отрицательные и дробные типы» . В статье рассматриваются типы сумм и типы товаров, в которых даны семантика для типов a - bи a/b. В отличие от сложения и умножения, существует не одна, а две инверсии возведения в степень, логарифмы и корни. Если типы...
Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 6 лет назад . Кажется, что многие люди считают, что , отчасти потому, что они считают, что факторинг не является разрешимым с помощью политикана. (Шива Кинтали...
Даны mmm от nnn двоичной матрицы MMM (записи являются 000 или 111 ), проблема в том , чтобы определить, существует два двоичных векторов v1≠v2v1≠v2v_1 \ne v_2 таким образом, что Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (все операции , выполняемые над ZZ\mathbb{Z} ). Эта проблема NP-сложная? Это ясно в NP,...
Есть ли пример языка, который есть в , но где мы не можем доказать этот факт непосредственно, показывая, что существует полиномиальное свидетельство о членстве в этом языке?NпNPNP Вместо этого тот факт, что язык находится в может быть доказан путем сведения его к другому языку в , где связь между...
Гротендик скончался . Он оказал огромное влияние на математику 20-го века, продолжая в 21-м веке. Этот вопрос задается в некотором стиле / духе, например, «Вкладов Алана Тьюринга в информатику» . Каковы основные влияния Гротендика на теоретическую информатику?...
Какие проблемы, как известно, принадлежат но не известны как принадлежащие P ?BPPBPP\mathsf{BPP}PP\mathsf P Точнее, меня интересуют независимые проблемы, то есть чьи дерандомизации, как известно, не эквивалентны. Например, известно, что дерандомизация PIT и многомерная полиномиальная факторизация...
Классическая задача quens задает, учитывая положительное целое число , существует ли массив чисел удовлетворяющий следующим условиям:nnnnnnQ[1..n]Q[1..n]Q[1..n] 1≤Q[i]≤n1≤Q[i]≤n1\le Q[i] \le n для всехiii Q[i]≠Q[j]Q[i]≠Q[j]Q[i] \ne Q[j] для всехi≠ji≠ji\ne j Q[i]−i≠Q[j]−jQ[i]−i≠Q[j]−jQ[i]-i \ne...
В моем компьютерном образовании я все чаще замечаю, что большинство дискретных задач являются NP-полными (по крайней мере), тогда как оптимизация непрерывных задач почти всегда легко достижима, обычно с помощью градиентных методов. Есть ли исключения из...
Я нашел эту статью очень интересной. Подводя итог: здесь обсуждается, почему на практике вы редко находите наихудший случай проблемы NP-полной. Идея в статье заключается в том, что экземпляры обычно либо сильно недооценены, либо сильно перенапряжены, и то, и другое относительно легко решить. Затем...
Я пытаюсь обернуть голову, в чем реальные различия между моделью актера параллелизма и моделью параллелизма последовательных процессов (CSP). На данный момент лучшее, что я смог придумать, это то, что модель актора позволяет изменять количество и расположение узлов, в то время как CSP имеет...
Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.kkkfff Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью...
Можно ли перевести булеву формулу B в эквивалентное соединение выражений Хорна? Статья в Википедии о HornSAT, похоже, подразумевает, что это так, но я не смог найти какую-либо ссылку. Обратите внимание, что я имею в виду не «за полиномиальное время», а скорее...
В настоящее время я читаю « Лямбда-исчисление и комбинаторы » Хиндли и Селдина. Я не эксперт, но всегда интересовался лямбда-исчислением из-за участия в функциональном программировании (начиная с Lisp и SICP, а теперь с R и Haskell). В « Binary лямбда - исчисления и комбинаторной логики» , Джон...