Я аспирант по математике, и теоретическая информатика - это область, в которой я никогда не понимал, о чем она, потому что не мог найти хорошее прочтение по этой теме. Я хочу знать, о чем этот домен на самом деле, какие темы он затрагивает, какие предпосылки необходимы для его запуска и т. Д. На...
В 2012 году Липтон написал статью в блоге о новом алгоритме решения линейных систем над конечными полями Прасада Рагхавендры. Ссылка на проект документа Raghavendra по этой теме теперь мертв , и я не могу найти что - нибудь по этой теме на сайте Raghavendra в. Является ли результат правильным?...
С чисто абстрактной математической / вычислительной точки зрения (как) можно даже узнать или рассуждать о таких проблемах, как 3-SAT, сумма подмножества, коммивояжер и т. Д.,? Сможем ли мы хоть как-то осмыслить их с функциональной точки зрения? Будет ли это вообще возможно? Я размышлял над этим...
Я задал этот вопрос 10 дней назад на cs.stackexchange здесь, но у меня не было никакого ответа. В очень известной статье (в сетевом сообществе) Wang & Crowcroft представили некоторые результаты полноты вычисления пути при нескольких аддитивных / мультипликативных ограничениях. Первая проблема...
Или, другими словами, у нас есть это для каждого языка и , или ?B A ≤ p B B ≤ p AAAAВВBA ≤пВA≤пВA \leq_p BB ≤пAВ≤пAB \leq_p
Я изучаю проблему, которая трудна для класса количественных логических формул с логарифмическим числом чередований кванторов. Проблема в этом классе будет выглядеть так: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xaжурналN)F\forall (x_1, x_2, \ldots...
Я нахожу несколько книг о компьютерах, но все они о технологиях. Я хочу что-то более связанное с
В моем вступлении к курсу по программированию мы изучаем метод инициализации-обслуживания-завершения, доказывающий, что алгоритм выполняет то, что мы ожидаем. Но нам осталось только доказать, что алгоритм, который уже известен как правильный, является правильным. Нас никогда не просили показать,...
Мы все знаем, что у есть барьеры. Мы все изучили эти барьеры, потому что мы считаем, что .P ≠ N Pп≠ NпP≠NPP\ne NPп≠ NпP≠NPP\ne NP Однако предположим, что и есть мудрые люди, которые считают, что такая возможность существует . Если это действительно так, то сам факт того, что мы не видели хороших...
У меня есть многогранник определенный как .PPP{x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} Вопрос: Учитывая вершину из P , есть ли алгоритм полиномиального времени для равномерной выборки из соседей v в графе P ? (Многочлен в измерении, число уравнений и представление б . Я могу...
Пусть G дерево на 2n вершинах. Ширина дерева G, tw (G) = 1. Теперь предположим, что мы добавляем n ребер в G, чтобы получить граф H. Легкая верхняя граница для tw (H) равна n + 1. Является ли это по существу наилучшим возможным? Как-то кажется, что tw (H) должно быть O (sqrt (n)), но это лишь...
Робин Милнер определил биграфы как тип графической структуры с графоподобной структурой, где узлы могут быть вложенными. Они обобщают исчисления процессов, такие как CCS и калькуляция, но Мильнер, похоже, намеревался использовать их гораздо более широко: в записках семинара незадолго до его смерти...
Рассмотрим , где lambda_i> 0 и Y_i распределены как стандартная нормаль. Какие границы концентрации можно доказать на X как функцию (фиксированных) коэффициентов lambda_i?Икс= ∑яλяY2яИксзнак равноΣяλяYя2X = \sum_i \lambda_i Y_i^2 Если все лямбда_i равны, то это граница Чернова. Единственный...
Если вы знакомы с проверкой программы, вы, скорее всего, предпочтете прочитать Вопрос перед тем, как начать . Если вы не знакомы с проверкой программы, возможно, вы все равно сможете ответить на этот вопрос, но, скорее всего, вы предпочтете сначала прочитать справочную информацию . Фон Часто...
Кто представил идею рекурсии ? Может кто-нибудь объяснить, откуда он взялся и как он повлиял на
В ответ на другой вопрос, « Расширения бета-теории лямбда-исчисления» , Евгений предложил ответ: бета + правило {s = t | s и t закрытые неразрешимые условия} где термин М разрешим , если мы можем найти последовательность терминов , такие , что M приложение «s для них равно I . Ответ Евгения дает...
Теорема Райса утверждает, что каждое нетривиальное свойство множества, распознаваемое некоторой машиной Тьюринга, неразрешимо. Я ищу теорему о сложности теории Райса, которая говорит нам, какие нетривиальные свойства NP-множеств...
Я студентка факультета компьютерных наук, и в настоящее время я планирую свой дипломный проект. Мне нужны некоторые идеи в области квантовых вычислений. любая...
Две статьи, которые я бы включил: Д. Козен, "Индексация субрекурсивных классов" , STOC, 1978. Р. Лэднер, "О структуре полиномиальной временной сводимости" , JACM, 1975....
Пытаясь исправить ошибку в библиотеке, я безуспешно искал документы по поиску поддиапазонов на красных и черных деревьях. Я рассматриваю решение с использованием застежек-молний и что-то похожее на обычную операцию добавления, используемую в алгоритмах удаления для неизменяемых структур данных, но...