Когда я думаю о программном обеспечении, которое небезопасно, я думаю, что оно «слишком полезно» и может быть использовано злоумышленником. Таким образом, обеспечение безопасности программного обеспечения - это процесс, который делает программное обеспечение менее полезным. В теоретической...
Для любого простого неориентированного графа G нетривиально определить, имеет ли G нетривиальные (неединичные) автоморфизмы. Но каковы результаты на верхних / нижних границах этой проблемы...
Барри Джей в своей книге делает несколько смелых заявлений - в основном, говоря, что в основе программы все является атомарным или составным. Тогда все можно легко итерировать, фильтровать, обновлять, просто перемещаясь по этим композиционным отношениям. Это новый рубеж в области компьютерных наук...
Лемма Джонсона-Линденштрауса грубо говорит о том, что для любого набора из точек в существует карта где такой, что для всех : Известно, что подобные выражения невозможны для метрики , но известно, есть ли способ обойти такое низкое значение границы, предлагая более слабые гарантии? Например, может...
Интересно, равны ли классы NPC, определенные сокращениями «многие-один» и сокращениями Тьюринга? Редактировать: Другой вопрос, являются ли сокращения Тьюринга только свертыванием классов C и co-C для некоторого C или существует класс такой как существует проблема не в при сокращении Карпа, а в в...
Во многих учебниках легко найти доказательства сокращения предмета и строгой нормализации для Системы F, а также иногда есть определения Системы F с парами, где (t, r) - это термин, а не только кодировка. Вопрос в том, что будет ссылкой на эту...
В графе независимое множество - это подмножество вершин, которое не содержит ребра в качестве индуцированного подграфа. Проблема нахождения наибольших независимых множеств в графе является фундаментальным и сложным в этом вопросе. Давайте рассмотрим более общий вопрос поиска (размера) наибольшего...
Какова точная временная сложность неориентированного алгоритма пространства журналирования st-связности Омера
Я только начал (независимое) изучение квантовых вычислений в целом из книги Нильсена-Чуанга. Я хотел спросить, может ли кто-нибудь попытаться найти время, чтобы помочь мне с тем, что происходит с постулатом измерения квантовой механики. Я имею в виду, я не пытаюсь поставить под сомнение постулат;...
(X,d)(X,d)(X, d)(Y,f)(Y,f)(Y, f)μ:X→Yμ:X→Y\mu : X \rightarrow Yμμ\muρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}ρ=maxp,q∈X{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)} \rho = \max_{p,q \in X} \{ \frac{d(x,y)}{f(\mu(x), \mu(y))}, \frac{f(\mu(x), \mu(y))}{d(x,y)} \} Есть и другие показатели качества:...
Мотивация для этого вопроса - факт, что большинство n-битных строк несжимаемо. Интуитивно, мы можем предложить по аналогии, что большинство доказательств тавтологии несжимаемы до полиномиального размера. По сути, моя интуиция заключается в том, что некоторые доказательства по своей природе случайны...
В то время как EE старшекурсник я посетил некоторые лекции, которые представили хорошую характеристику булевых схем с точки зрения, сколько у них вложенных циклов. По своей сложности булевы схемы часто считаются дагами, но в реальных аппаратных циклах это обычное явление. Теперь, по модулю...
Я считаю, что ответ на этот вопрос хорошо известен; но, к сожалению, я не знаю. В квантовых вычислениях мы знаем, что смешанные состояния представлены матрицами плотности. А следовая норма разности двух матриц плотности характеризует различимость двух соответствующих смешанных состояний. Здесь...
Для заданного графа в задаче сепаратора задается вопрос, существует ли вершина или множество ребер малой мощности (или веса), удаление которых разбивает на два непересекающихся графа приблизительно равных размеров. Это называется проблемой разделения вершин, когда удаленный набор является набором...
Я разработал новую методику дерандомизации, которая нацелена на рекурсивные рандомизированные алгоритмы (или) более общие рандомизированные алгоритмы, которые используют стек. К сожалению, я не смог найти естественные рандомизированные алгоритмы для применения моих методов. Рекурсивные цепи Маркова...
Представьте себе функциональный язык программирования, единственными типами данных которого являются числовые скаляры и произвольные вложения массивов. В языке отсутствуют какие-либо средства неограниченной итерации, поэтому запрещено следующее: явные циклы (во всяком случае, без побочных эффектов)...
Это может звучать больше как вопрос социальных наук, чем вопрос TCS, но это не так. Читая « Рандомизированные алгоритмы », описывающие проблему стабильного брака, можно прочитать следующее (p54) «Можно показать, что для каждого списка предпочтений существует, по крайней мере, один стабильный брак....
В разделе 2.2 B-деревьев , забывающих о кеше, деревья поиска с сильно сбалансированным весом определяются как: Для некоторой константы каждый узел v на высоте h имеет Θ ( d h ) потомков.dddvvvhhhΘ(dh)Θ(dh)\Theta(d^h) Они утверждают: Деревья поиска, которые удовлетворяют свойствам 1 и 2, включают...
Я начинаю свои исследования теории алгоритмических игр, и кажется, что обычно принимается концепция равновесия с неподвижной точкой на графе. Однако смотрели ли люди на альтернативные концепции равновесия, такие как предельные циклы? Я могу себе представить, что «жесткий» предельный цикл, то есть...
Некоторое время я разрабатывал алгоритм SAT и дошел до того, что хотел бы им поделиться. Я не знаю многих людей в области компьютерных наук, и я не уверен, куда именно обратиться. Мне интересно, какие ресурсы доступны для человека с алгоритмом, который рассматривает возможность публикации. Мне...