В распределенных вычислениях проблема консенсуса, по-видимому, является одной из центральных тем, которая привлекла интенсивные исследования. В частности, статья «Невозможность распределенного консенсуса с одним ошибочным процессом» была удостоена награды PODC за выдающуюся работу в 2001 году . Так...
В разделе « Семантика» Энтони Ааби «Введение в языки программирования» он делает следующее наблюдение: Большая часть работы в семантике языков программирования мотивируется проблемами, возникающими при попытке построить и понять императивные программы - программы с командами присваивания. Поскольку...
Правильно ли я понимаю, что доказательство того, что задача NP завершена, является успехом исследования? Если так, то
Я искал далеко и широко для таких приложений и в основном оказался коротким. Я могу найти множество применений топологии и подобных структур на счетных (или неисчисляемых) наборах, но редко я нахожу неисчислимые наборы в качестве объекта изучения компьютерными учеными, что приводит к необходимости...
Теория сложности, кажется, отражает нечто фундаментальное в структуре вселенной, поскольку она формализует интуитивное представление о том, что некоторые проблемы сложнее других. Скотт Ааронсон предсказал : «Предположение о твердости NP в конечном итоге будет рассматриваться как аналог Второго...
Этот вопрос вдохновлен Технологическим Центром Джорджии и Центром Случайности футболкой , которая спрашивает «Рандомизировать или нет ?!» Есть много примеров, когда рандомизация помогает, особенно при работе в состязательной среде. Есть также некоторые настройки, в которых рандомизация не помогает...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
Фон . Я студент бакалавриата, который интересуется исследованиями, связанными с теорией категорий, монадами и Хаскеллом, и я хочу найти тему для своей диссертации бакалавра в этой области. Я посмотрел на бумагу Эудженио Могги , « Понятия вычислений и монад », 1991, и я пока не очень разбираюсь в...
В настоящее время я учусь в средней школе, интересуюсь теоретической информатикой и прикладной математикой. Я сам учил себя линейной алгебре и исчислению и конкретной математике. У меня есть наивное представление о том, что для того, чтобы писать лучшие алгоритмы, нужно знать как можно больше...
Я всегда заинтригован отсутствием численных доказательств в экспериментальной математике за или против вопроса P против NP. В то время как гипотеза Римана имеет некоторые подтверждающие данные из численной проверки, я не знаю аналогичных доказательств для вопроса P против NP. Кроме того, мне...
вычислительная сложность включает в себя большое количество комбинаторики и теории чисел, некоторые особенности стохастики и растущее количество алгебры. Однако, будучи аналитиком, мне интересно, есть ли приложения анализа в этой области, или, может быть, идеи, вдохновленные анализом. Все, что я...
Будучи из физики, я был обучен изучать множество проблем с геометрической точки зрения. Например, дифференциальная геометрия многообразий в динамических системах и т. Д. Когда я читаю основы информатики, я всегда пытаюсь найти геометрические интерпретации. Как правдоподобная геометрическая...
Я вспоминаю, как видел исследование или статью, где недавно утверждалось, что большая часть ускорения, наблюдаемого в компьютерных программах за последние несколько десятилетий, происходит от более совершенных алгоритмов, а не от более быстрого аппаратного обеспечения. Кто-нибудь знает исследование...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Мне кажется, что большинство теоретиков сложности обычно верят в следующее философское правило: Если мы не можем найти эффективный алгоритм для задачи и можем свести проблему A к проблеме B , то, вероятно, эффективного алгоритма для проблемы B тоже нет.AAAAAABBBBBB Вот почему, например, когда новая...
Мой первый вопрос: известна ли интерактивная характеристика системы доказательств для всех классических классов сложности. Я бы назвал P, NP, PSPACE, EXP, NEXP, EXPSPACE рекурсивными и рекурсивно перечислимыми функциями классическими (среди прочих). В частности, известна ли интерактивная...
За пределами академического сообщества, какова польза от моих «способностей»? Что я могу сделать кроме обучения и публикации статей? Где все я могу применить свои полномочия? Для аргументации: пожалуйста, предположим, что у меня есть докторская степень в алгоритмах / TCS, я выучил много «вещей» и...
Что такое теоретическая информатика? Это обучение кодированию на разных языках и создание приложений на платформах? Или это просто думать о более быстрых и быстрых алгоритмах, чтобы вы могли более эффективно решать задачи с помощью компьютеров? Или это программирование и размышление о новых...
Предположим, вы встречаетесь с программистами, которые прошли некоторые профессиональные курсы по программированию (или думали сами), но не изучали математику университетского уровня. Чтобы показать им всю прелесть TCS, я хотел бы собрать некоторые хорошие результаты / открытые вопросы, поступающие...
Пусть - булева функция с чувствительностью s ( f ) и чувствительностью блока b s ( f ) .еffs ( f)s(f)s(f)b s ( f)bs(f)bs(f) Гипотеза о чувствительности блока чувствительности утверждает, что существует такое , что ∀ f , b s ( f ) ≤ s ( f ) c .с > 0c>0c>0∀ ф, b s ( f ) ≤ s (...