Мне было интересно, какие бумаги я должен прочитать, чтобы понять этот вопрос Неожиданная связь с другими областями математики, такими как алгебраическая геометрия или высшие когомологии. Возможно, даже область математики еще не разработана. Возможно, кто-то разработает совершенно новое направление...
Читая ответ Питера Шора и предыдущий вопрос Адама Крума, я понял, что у меня есть некоторые неправильные представления о том, что значит быть -hard.PP\mathsf{P} Проблема -hard, если любая проблема в сводится к ней с помощью (или если вы предпочитаете ) сокращений. Проблема находится вне если не...
Речь идет о том, как эффективно мы можем выразить алгоритм под рукой. Мне нужно это для моего обучения студентов. Я понимаю, что нет такой вещи, как стандартный способ написания псевдокода. Разные авторы следуют различным соглашениям. Было бы полезно, если бы люди указывали на то, как они следуют и...
Состояние наших знаний об общих арифметических схемах похоже на состояние наших знаний о булевых схемах, то есть у нас нет хороших нижних границ. С другой стороны, мы имеем экспоненциальный размер нижних границ для монотонных булевых цепей . Что мы знаем о монотонных арифметических схемах? У нас...
Поскольку он не допускает вычислений без прерывания, Coq обязательно не является тьюрингово-полным. Какой класс функций может вычислять Coq? (есть интересная характеристика...
PPPXX\mathcal{X}AA\mathcal{A}PPPDD\mathcal{D}RR\mathcal{R}AA\mathcal{A}minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x)...
Я читал « Является ли P против NP формально независимым? », Но я был озадачен. В теории сложности широко распространено мнение, что . Мой вопрос о том, что, если это не доказуемо (скажем, в ). (Предположим, что мы только узнаем, что не зависит от но никакой дополнительной информации о том, как это...
Когда я возился с неканоническим анализом LR, я придумал метод синтаксического анализа (с таблицами бесконечного размера, что делает его несколько непрактичным ), способный анализировать ровно однозначные грамматики за времени, и мне было интересно, возможно ли это сделать лучше:O(n2)O(n2)O(n^2)...
В игре Tower Defense у вас есть сетка NxM с началом, финишем и несколькими стенами. Враги выбирают кратчайший путь от начала до конца, не проходя сквозь стены (обычно они не привязаны к сетке, но для простоты, скажем, так. В любом случае они не могут перемещаться через диагональные «дыры») Задача...
Меня интересует сложность определения того, является ли данный непростой многоугольник почти простым, в любом из двух различных формальных значений: слабо простой или несамопересекающийся . Поскольку эти термины широко не известны, позвольте мне начать с некоторых определений. Многоугольник...
Есть много результатов неприемлемости, которые основаны на гипотезе об уникальных играх. Например, Предполагая гипотезу об уникальных играх, трудно вычислить аппроксимацию задачи максимального разреза в пределах коэффициента R для любой константы R > R GW . (Здесь R GW = 0,878… - коэффициент...
Кто-нибудь знает ссылки, в которых четко прописана связь между алгоритмом объединения и гауссовым исключением? Меня особенно интересует связь между треугольными заменами и LU-разложениями. Уэйн Снайдер и Джин Галлиер упоминают эту аналогию в своей статье « Возвращение к объединению высшего порядка:...
Во время тестирования свойств графов, алгоритм запрашивает целевой график на наличие или отсутствие ребер и потребностей , чтобы определить , либо имеет ли целевые определенное свойство или εε\epsilon -far от того , свойства. (Алгоритм можно попросить преуспеть с 1-сторонней или 2-сторонней...
Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...
Есть ли полезное описание будущего или обещания с точки зрения теории категорий? В частности, каким может быть категорический дуал
Кубические графы - это графы, в которых каждая вершина имеет степень 3. Они были тщательно изучены, и я знаю, что некоторые NP-сложные задачи остаются NP-трудными, даже если они ограничены подклассами кубических графов, но некоторые другие становятся проще. Суперкласс кубических графов - это класс...
Я ищу неориентированные, невзвешенные связные графы , в которых для каждой пары существует уникальный путь который реализует расстояние ,G=(V,E)G=(V,E)G=(V,E)u,v∈Vu,v∈Vu,v \in Vu→vu→vu \rightarrow vd(u,v)d(u,v)d(u,v) Этот класс графиков хорошо известен? Какие еще свойства у него есть? Например,...
Рассмотрим электрическую сеть, смоделированную как планарный граф G, где каждое ребро представляет собой резистор 1 Ом. Как быстро мы можем вычислить точное эффективное сопротивление между двумя вершинами в G? Эквивалентно, как быстро мы можем вычислить точный ток, протекающий вдоль каждого края,...
В свете недавней пропасти на глубине 3 результата (который, среди прочего, дает глубины 3 арифметическая схема дляп×попределителя надС), у меня следующие вопросы: Григорьев и Карпиньскидоказалв2Ом(п)нижняя граница для любой глубины-3 арифметической схемы вычислительной Определительп×пматрицы над...
Я ищу краткий вводный текст об алгоритмах с высоким отношениемОн должен начинаться с самого начала, но затем быстро развиваться, не тратя слишком много времени на примеры из реального мира, методики элементарных доказательств и т. Д. Как математик-исследователь, у меня есть глубокие знания в...