В главе 13 «Атомные объекты» книги «Распределенные алгоритмы» Нэнси Линч доказано, что линеаризуемость (также известная как атомарность) является свойством безопасности. То есть его соответствующее свойство trace непусто, закрыто по префиксу и закрыто по пределу , как определено в разделе 8.5.3....
Каково стандартное определение Planar 3-SAT? Я видел много разных определений. Какая оригинальная статья определила ее и доказала, что она является
Существуют ли проблемы, которые разрешимы за полиномиальное время, только если P! = NP, и иначе разрешимы за (скажем) времени?O(2n)O(2n)O(2^n) Простым примером может быть: Если P! = NP, вычислите тест на простоту для случайного n-разрядного числа, в противном случае оцените случайную позицию...
Я пытаюсь найти распределение по Nnn случайным векторам, скажем, Икс1, … , ХNx1,…,xnx_1,\ldots, x_n , на Кkk мерной единичной сфере (где н > кn>kn > k ), которое минимизирует Максимумя ≠ jV a r ( xTяИксJ)maxi≠jVar(xiTxj)\max_{i\neq j} \mathrm{Var}(x_i^T x_j) при условии ограничения Э [...
Справочная информация: обработка транзакций была традиционной темой исследования в теории баз данных. В настоящее время распределенные транзакции популяризируются крупномасштабными распределенными системами хранения, которые обычно включают разделение данных (также называемое разделением ) и...
В статье 1965 года " О вычислительной сложности алгоритмов " Хартманиса и Стернса авторы предполагают, что если машина Тьюринга в реальном времени вычисляет действительное число , например, в базе 10, то является либо рациональным числом, либо трансцендентное число.rrrrrr Существует ли вычислимое...
Доказательство сложности является основной областью теории вычислительной сложности. Конечная цель этой области состоит в том, чтобы доказать , то есть любой доказатель не может дать доказательство неудовлетворенности данной входной формулой. Nп≠ c o NпNп≠соNпNP\neq coNP Граф - это одна из...
Это довольно известный факт, что для получения противоречия из неравенства (например, ) в теории типов Мартина-Лоэфа требуется вселенная.( 0 =1 ) → ⊥(0=1)→⊥(0=1) \to \bot Доказательство также довольно простое - в отсутствие юниверсов мы можем стереть зависимости из любого зависимого типа, чтобы...
Рассмотрим следующую проблему: Учитывая матрицу мы хотим оптимизировать количество сложений в алгоритме умножения для вычисления v ↦ M v .MMMv↦Mvv↦Mvv \mapsto Mv Я нахожу эту проблему интересной из-за ее связи со сложностью умножения матриц (эта проблема является ограниченным вариантом умножения...
Рассматриваемые здесь преобразователи - это те, которые Википедия называет преобразователями конечного состояния . Поведение преобразователя , то есть вычисляемого им отношения, записывается как [ T ] : слово y является выходом для x тогда и только тогда, когда x [ T ] y...
Где я могу найти введение в вероятностные автоматы и что они распознают (определенные функции из слов в )? Существует ли стандартный термин для таких функций, которые распознаются вероятностными автоматами, аналогично «обычным языкам» для того, что распознают детерминированные конечные автоматы...
Позволять ЧАСA LTNHALTnHALT_n обозначить строку длины 2N2n2^n соответствует таблице истинности проблемы остановки для входов длины Nnn, Если последовательность колмогоровских сложностей К( HA LTN)K(HALTn)K(HALT_n) мы O ( 1 )O(1)O(1), тогда одна из строк рекомендаций будет использоваться бесконечно...
Предположим, что - параметризованный язык относительно некоторого алфавита Σ . К -slice из L является L K = L ∩ { ( х , к ) | х ∈ Е * } , множество экземпляров в L , которые имеют параметр K . Класс сложности X P содержит параметризованные языки L такие, что L k ∈ P для каждого...
Мотивация : Разрабатывая инструменты для управления версиями данных, мы в конечном итоге изучили алгоритмы «различий» двух наборов целых чисел, предложив последовательность преобразований, которые переводят один набор целых чисел в другой. Мы смогли свести эту проблему к следующей очень...
Термин « инверсия программы» имеет несколько оттенков смысла, но, вероятно, он начался с работы Дж. Маккарти 1956 года «Обращение функций, определенных машинами Тьюринга в контексте ИИ». К настоящему времени обнаружено множество связей между инверсией программы и другими областями, например,...
Я нахожусь в ситуации, когда мне нужно показать, что проверка типов решаема для исчисления с зависимым типом, над которым я работаю. До сих пор я был в состоянии доказать, что система сильно нормализуется, и, таким образом, равенство определений разрешимо. Во многих ссылках, которые я читал,...
Мне интересно, может ли кто-нибудь подсказать мне, почему строгая положительность индуктивных типов данных гарантирует строгую нормализацию. Чтобы было ясно, я вижу, как наличие отрицательных явлений приводит к расхождению, то есть путем определения: data X where Intro : (X->X) -> X мы можем...
Я (медленно) пишу обзор Руководства по алгоритмам хемоинформатики для новостей SIGACT. В одной главе рассматриваются текущие реализации программного обеспечения, и поиски в базе данных (и другие приложения), по-видимому, не используют столько информации о графиках, сколько могли бы. С другой...
Предположим, нам дан график и параметры . Существуют ли диапазоны значений для (или это выполнимо для всех ), для которых можно проверить, является ли -far из-за наличия независимого набора размера по крайней мере во времени ?ггGк , ϵК,εk,\epsilonККkККkггGεε\epsilonККkO ( n + поли ( 1 / ϵ )...
Интересно, есть ли у них какие-либо подходы, формулирующие проблему маршрутизации транспортного средства с временными окнами ( VRPTW ) (как проблему решения) в качестве экземпляра SAT / SMT? (альтернатива: TSP) Например: «Есть ли правильное решение для посещения всех клиентов в пределах их...