В настоящее время я пытаюсь найти полные задачи EXPSPACE (в основном, чтобы найти вдохновение для сокращения), и я удивлен небольшим количеством ожидаемых результатов. Пока я нашел это, и у меня есть проблемы с расширением списка: универсальность (или другие свойства) регулярных выражений с...
В настоящее время этот вопрос не очень подходит для нашего формата вопросов и ответов. Мы ожидаем, что ответы будут подтверждены фактами, ссылками или опытом, но этот вопрос, скорее всего, вызовет дебаты, споры, опрос или расширенное обсуждение. Если вы считаете, что этот вопрос можно улучшить и,...
Вдохновленный этим вопросом , каковы основные проблемы и существующие решения, которые нуждаются в улучшении в (теоретической) области распределенных систем. Что-то вроде протоколов членства, согласованности...
Где я могу найти графики, относящиеся к реальным проблемам? Я знаю два репозитория: Коллекция разреженных матриц Университета Флориды Bodlaender в TreewidthLib
Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос! Сокращения всех видов приветствуются. Я начну с действительно простого сокращения от...
Я ищу языки, которые "вероятно, не являются контекстно-свободными", но мы не можем (не) доказать это, используя известные стандартные методы. Есть недавний опрос на предмет или открытый проблемный раздел от недавней конференции? Вероятно, не так много языков, которые не известны как CF, поэтому,...
Есть много мест, где числа ππ\pi и (1+5–√)/2(1+5)/2(1+\sqrt5)/2появляются. Мне любопытно узнать об алгоритмах, время выполнения которых содержит золотое сечение илиππ\piв показателе...
Я использовал Jung ( http://jung.sourceforge.net/ ) для визуализации ранга страницы, и мне показалось немного медленным и трудным масштабировать его за пределы 100 узлов. Мне было интересно, какие другие инструменты люди используют для анализа и визуализации сетей / социальных...
В этом вопросе мы, кажется, идентифицировали естественную проблему, которая является NP-полной при рандомизированных сокращениях, но, возможно, не при детерминированных сокращениях (хотя это зависит от того, какие недоказанные предположения в теории чисел верны). Известны ли еще такие проблемы?...
Locked . Этот вопрос и его ответы заблокированы, потому что вопрос не по теме, но имеет историческое значение. В настоящее время он не принимает новые ответы или взаимодействия. Какие алгоритмы используются чаще всего? Пожалуйста, напишите один алгоритм для каждого ответа, постарайтесь, чтобы ваш...
Я думаю, что было бы неплохо составить список теорем, утверждающих, что P не равен NP, если и только если такие и такие выходы существуют, некоторый класс сложности содержится в другом классе сложности и так далее, и так далее....
В каких университетах существует сильная учебная программа по квантовым вычислениям и предлагаются какие-либо курсы / исследования по квантовым вычислениям? Цель здесь - собрать полезный список для тех, кто рассматривает аспирантуру в этих областях, а не для обсуждения того, что является «лучшим»....
Я хотел бы знать, были ли предположения, которые давно не были доказаны в TCS, которые позже были подтверждены следствием другой теоремы, что, возможно, было легче доказать....
Я никогда раньше не видел алгоритм с логом в знаменателе, и мне интересно, есть ли какие-нибудь действительно полезные алгоритмы с этой формой? Я понимаю много вещей, которые могут привести к умножению логарифмического коэффициента во время выполнения, например, сортировка или алгоритмы на основе...
Я аспирант по математике с твердым опытом в логике. Я прошел годичный курс для выпускников по логике вместе с курсами для выпускников по теории конечных моделей и другим курсам по принуждению и теории множеств. Большинство текстов CS, кажется, предполагают только очень скромный фон в логике,...
Существуют ли какие-либо предположения в теоретической информатике, которые включают некоторый параметр n и были доказаны для малых значений n AND для простых чисел, но позже оказались ложными? В теории чисел такие проблемы существуют, например. как Аарон Мейеровиц указывает на один из...
Какие основные открытые проблемы вычислительной сложности возникают из-за языков программирования, особенно из анализа и компиляции программ? Я ищу проблемы по линии «временная сложность вывода типа Хиндли-Милнера» или «временная сложность 0CFA» (хотя обе проблемы...
Ларри Вассерман недавно опубликовал пост, где рассказывает о «полиции p-значения». Он делает интересное замечание (все выделено мной) (предпосылка, которую я добавил курсивом, и его ответ под ним): Наиболее распространенная жалоба состоит в том, что физики и журналисты неправильно объясняют...
Каковы некоторые основные примеры успешной дерандомизации или, по крайней мере, прогресса в демонстрации конкретных доказательств достижения цели (а не связи между случайностью и жесткостью)?п= B Pппзнак равноВппP=BPP Единственный пример, который мне приходит в голову, - это тестирование AKS на...
k = √max { k , n / k }max{k,n/k}\max \left\{k, n/k\right\}k = n--√k=nk=\sqrt n алгоритм гигантского шага baby-step для вычисления дискретного логарифма в O ( n--√)O(n)O(\sqrt n) , статический двухмерный ортогональный отсчет во времени O ( n--√)O(n)O(\sqrt n) и памяти O ( n )O(n)O(n) , приоритетная...