Насколько хорошо была исследована следующая проблема в TCS? (Я извиняюсь, если постановка проблемы звучит расплывчато!) При наличии модели вычислений MC (машина Тьюринга, сотовые автоматы, машина Колмогорова-Успенского ... и т. Д.) И модели шума, которая может повлиять на вычисление MC, существует...
Пусть - формула CNF с n переменными и m предложениями. Пусть t ∈ { 0 , 1 } n представляет присваивание переменной, а f φ ( t ) ∈ { 0 , … , m } подсчитывает количество предложений, удовлетворяемых присваиванием переменной φ . Затем определите Median-SAT как задачу вычисления медианного значения f φ...
Рассмотрим # P-полную задачу подсчета числа покрытий вершин данного графа .G=(V,E)G=(V,E)G = (V, E) Я хотел бы знать, есть ли какой-либо результат, показывающий, как сложность такой проблемы изменяется с некоторым параметром (например, d = | E |GGG).d=|E||V|d=|E||V|d = \frac{|E|}{|V|} У меня такое...
Рассмотрим следующий естественный вопрос: для какого конечного языка наименьшая не зависящая от контекста грамматика порождает L ?LLLLLL Мы можем сделать вопрос более интересным, указав последовательность языков , например, L n - это множество всех перестановок { 1 , … , n } : интуитивно, CFG для L...
Известны ли результаты, которые исключают существование «слишком хороших, чтобы быть правдивыми» структур данных? Например: можно ли добавить функциональность и J o i n в структуру данных ведения заказа (см. Dietz and Sleator STOC '87 ) и при этом получить O ( 1 ) временных операций?Sp l i...
Я уже задавал этот вопрос на stackoverflow , но, возможно, он лучше подходит для этого сайта. Проблема в: У меня N пар целых чисел без знака. Мне нужно их отсортировать. Конечный вектор пар должен сортироваться неуклонно по первому числу в каждой паре и неуклонно по второму в каждой паре. Каждая...
Пусть G будет ненаправленным графом из n узлов, и пусть T будет подмножеством узлов V (G), называемых терминалами . Сохранитель расстояния (G, T) - это граф H, удовлетворяющий свойству dЧАС( u , v ) = dграмм( ты , ты )dЧАС(U,v)знак равноdграмм(U,v)d_H(u,v) = d_G(u,v) для всех узлов u, v в T....
Две части TCS - это алгоритмы и сложность. Я упрощенно скажу, что алгоритмы - это исследование верхних границ, показывающее, что вы можете что-то сделать (с заданными ограниченными ресурсами), а сложность заключается в том, чтобы показать, что вы не можете сделать это без каких-либо минимальных...
Существует красивая теорема Кобе (см. Здесь ), которая гласит, что любой плоский граф можно нарисовать как целующий граф дисков (очень романтично ...). (Другими словами, любой плоский граф может быть нарисован как граф пересечений дисков.) Теорема Кебе не очень легко доказать. Мой вопрос:...
Я заинтересован в реализации SM для задачи LP, однако я слышал о возможных подводных камнях: книга Кормена говорит, что возможно иметь входные данные, которые приведут к тому, что наивная реализация будет вести себя экспоненциально. Я также слышал, что наивная реализация может зацикливаться на...
Я заинтересован в оптимизации потоков данных и потоков управления графами и, в частности, более сложными в вычислительном отношении. Но также будет интересно узнать о последних изобретениях в области оптимизации...
Что-нибудь известно о следующей проблеме? Имеет ли это смысл вообще? Как это называется? Это тривиально эквивалентно какой-то другой проблеме? Что такое сложность времени? Для заданного неориентированного (общего / плоского / ограниченной степени / и т. Д.) Графа G = (V, E) найдите максимальное...
Грег Иган в своей художественной литературе «Темные целые» (рассказ о двух вселенных, в которых две разные математики общаются посредством доказательства теорем о непоследовательности в арифметике) утверждает, что можно построить компьютер общего назначения исключительно на существующих...
В последнее время я имел дело с алгоритмами, связанными со сжатием, и мне было интересно, какая наилучшая степень сжатия может быть достигнута при сжатии данных без потерь. До сих пор единственным источником, который я мог найти по этой теме, была Википедия: Сжатие без потерь оцифрованных данных,...
Учитывая неориентированный регулярный граф , какова связь между его диаметром - определенным как наибольшее расстояние между двумя узлами - и его проводимостью, определенной как где e (S, S ^ c) - количество ребер, пересекающих S и S ^ c...
Давно известно, что при любой степени восстановления существует конечно представленная группа, проблема слова в которой есть в этой степени. У меня вопрос: верно ли то же самое для произвольных полиномиальных степеней Тьюринга? В частности, существует ли разрешимое множество , существует ли конечно...
Я готовлю некоторые учебные материалы по эвристике для оптимизации и изучаю методы координатного спуска. Здесь настройка представляет собой многовариантную функцию которую вы хотите оптимизировать. f имеет свойство, ограниченное какой-либо одной переменной, его легко оптимизировать. Таким образом,...
В хеш-таблицах, которые разрешают коллизии линейным зондированием, для обеспечения ожидаемой производительности необходимо и достаточно, чтобы хеш-функция была из 5-независимого семейства. (Достаточность: «Линейное зондирование с постоянной независимостью», Паг и др. , Необходимость: «О...
В теории комбинаторного представления и алгебраической геометрии существует ряд проблем, для которых не существует положительной формулы. Есть несколько примеров, о которых я думаю, но позвольте мне взять в качестве примера вычисление коэффициентов Кронекера . Обычно понятие «положительная формула»...
У Бейджи, Шора и Уотруса есть очень хорошая статья о силе квантовых интерактивных доказательств с короткими сообщениями. Они рассматривают три варианта «коротких сообщений», и один из них, который меня волнует, - это их второй вариант, в котором может быть отправлено любое количество сообщений, но...