Когда мы рассматриваем алгоритм аппроксимации для задачи минимизации, разрыв интегральности IP-формулировки для этой задачи дает нижнюю границу отношения аппроксимации для определенного класса алгоритмов (таких как алгоритм округления или простой двойственный алгоритм). На самом деле существует...
Предположим , что мы имеем полиномы степени не более n , n > m , так что общее число ненулевых коэффициентов равно n (т. е. многочлены редки). Меня интересует эффективный алгоритм вычисления полинома:p1,...,pmp1,...,pmp_1,...,p_mnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Поскольку...
Я думаю, что теорема об иерархии размеров для сложности схемы может быть главным прорывом в этой области. Это интересный подход к разделению классов? Мотивация вопроса заключается в том, что мы должны сказать есть некоторая функция, которая не может быть вычислена схемами размера и может быть...
Есть ли способ доказать следующую теорему в Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. РЕДАКТИРОВАТЬ : Попытка дать краткое объяснение «что такое доказательство неуместности» (поправьте меня, если я ошибаюсь или неточен) Основная идея заключается в том, что в мире...
У меня много кубоидов в трехмерном пространстве, у каждого есть начальная точка в (x, y, z) и размер (Lx, Ly, Lz). Интересно, как найти самый большой куб в этом трехмерном пространстве, который содержится в объединении кубоидов. Есть ли эффективный алгоритм для этого? Например, если у меня есть...
Хорошо известно, что если то иерархия полиномов разрушается и .P = N PP=NP\mathbf{P}=\mathbf{NP}P = P HP=PH\mathbf{P}=\mathbf{PH} Это можно легко понять индуктивно с помощью оракулов. Вопрос в том, почему мы не можем продолжить индуктивный процесс за пределами постоянного уровня чередований и...
Может кто-нибудь объяснить кратко (если это возможно!) Или отослать меня к ссылке, обобщающей различия между нетипизированным лямбда-исчислением и более распространенным типизированным лямбда-исчислением? Я особенно ищу заявления об их выразительной силе, эквивалентности логическим / арифметическим...
Я рассматриваю Справочник по естественным и инновационным вычислениям для SIGACT News. Это очень интересное чтение. Каждая глава, тем не менее, имеет вкус: «Это моя область исследований, и, черт возьми, это круто!» Таким образом, часть того, что я пытаюсь сделать, - выделить шумиху и сделать...
В 1979 году Фрейвалдс показал, что верификация матричных произведений по любому полю может быть выполнена за рандомизированное время . Более формально, учитывая три матрицы A, B и C, с записями из поля F, проблема проверки, имеет ли AB = C случайный O ( n 2 ) алгоритм...
Моему 8-летнему надоело создавать обычные лабиринты, и он занялся созданием вариантов, которые выглядят так: Идея состоит в том, чтобы начать с x и достичь o по обычным правилам. Кроме того, вы можете переходить с любого целого числа aaa на любое другое целое число ббb , но вы должны заплатить |...
Это переформулировка программ грамматики? предыдущий вопрос от Vag и множество предложений от комментаторов. Каким образом грамматика может рассматриваться как спецификация модели вычислений? Если, например, мы берем простую контекстно-свободную грамматику, такую как G ::= '1' -> '0' '+' '1'...
Это можно считать глупым вопросом. Я не специализируюсь в области компьютерных наук (и еще не изучаю математику), поэтому, пожалуйста, извините, если вы считаете, что следующие вопросы отражают некоторые ошибочные предположения. Хотя есть планы формализовать последнюю теорему Ферма (см. Эту...
Недавний подход к созданию децентрализованной онлайн-валюты под названием биткойн вызвал некоторый интерес. Цель состоит в том, чтобы иметь возможность переводить валюту без центрального органа и без двойных расходов или подделок. Их подход заключается в том, чтобы все узлы в сети пытались...
Здесь цель состоит в том, чтобы свести произвольную задачу SAT к 3-SAT за полиномиальное время, используя наименьшее количество предложений и переменных. Мой вопрос мотивирован любопытством. Менее формально я хотел бы знать: «Каково« наиболее естественное »сокращение с SAT до 3-SAT?» Теперь...
(n+1)(n+1)(n + 1) точек необходимы для однозначного определения многочлена степени ; например, две точки на плоскости определяют ровно одну линию.nnn Сколько точек требуется для однозначного определения вычислимой функции , учитывая длину программы, которая вычисляет на фиксированном языке? (т.е....
Работать напрямую со сложностью времени или нижними границами схемы страшно. Следовательно, мы разрабатываем такие инструменты, как сложность запросов (или сложность дерева решений), чтобы справиться с нижними границами. Поскольку каждый запрос занимает по крайней мере один блок-шаг, а вычисления...
Просто из любопытства, если классические вычисления основаны на матрицах перестановок, а квантовые вычисления - на унитарных матрицах (из которых матрицы подстановок являются подгруппой), то будет ли какая-либо парадигма вычислений помимо унитарных...
РЕДАКТИРОВАТЬ (22 августа 2011 г.): Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу...
Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...
Какова сложность (в стандартном целочисленном ОЗУ) вычисления стандартного дискретного преобразования Фурье вектора из nNn целых чисел? Классический алгоритм для быстрых преобразований Фурье , неуместно [1] приписываемый Кули и Тьюки, обычно описывается как выполняющийся за O(nlogn)О(NжурналN)O(n...