С общей точки смысле зрения, легко поверить , что добавление индетерминизм к значительно расширяет свою власть, т.е. N P гораздо больше , чем P . В конце концов, недетерминизм допускает экспоненциальный параллелизм, который, несомненно, кажется очень мощным. PP\mathsf{P}NPNP\mathsf{NP}PP\mathsf{P}...
Рассмотрение вопросов через алгоритмическую линзу (то есть с алгоритмической или сложной точки зрения) стало полезным в дисциплинах вне «стандартной области» информатики. В частности, CS оказал влияние на биологию с помощью вычислительной биологии, на физику с помощью квантовой обработки...
Я иногда слышал, как люди говорят о квантовых алгоритмах, о состояниях и о способности рассматривать несколько возможностей одновременно, но мне так и не удалось найти кого-то, кто мог бы объяснить вычислительную модель, стоящую за этим. Чтобы было ясно, я не спрашиваю о том, как физически...
Многие эксперты считают, что гипотеза верна, и используют ее в своих результатах. Меня беспокоит то, что сложность сильно зависит от гипотезы P ≠ N P.PNPP≠NP\mathsf{P} \neq \mathsf{NP}PNPP≠NP\mathsf{P} \neq \mathsf{NP} Итак, мой вопрос: Пока гипотеза не доказана, можно / нужно ли рассматривать ее...
Одна из приятных сторон эволюции во вселенной с тремя пространственными измерениями заключается в том, что мы развили навыки решения проблем, относящихся к объектам в космосе. Таким образом, например, мы можем думать о триплете чисел как о точке в 3-м и, следовательно, вычисление о триплетах чисел...
Меня интересует, почему натуральные числа так любимы авторами книг по теории языков программирования и теории типов (например, Дж. Митчелл, Основы языков программирования и Б. Пирс, Типы и языки программирования). Описание простейшего лямбда-исчисления и, в частности, языка программирования PCF...
Изучение экологии и эволюции становится все более математическим, но большинство теоретических инструментов, похоже, исходит от физики. Однако во многих случаях проблемы носят весьма дискретный характер (см., Например, SLBS00 ) и могут быть полезны с точки зрения информатики . Тем не менее, я знаю...
Гротендик скончался . Он оказал огромное влияние на математику 20-го века, продолжая в 21-м веке. Этот вопрос задается в некотором стиле / духе, например, «Вкладов Алана Тьюринга в информатику» . Каковы основные влияния Гротендика на теоретическую информатику?...
Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних...
Какие последствия может иметь доказательство гипотезы abc для tcs?
Существует множество применений реального анализа в теоретической информатике, охватывающих тестирование свойств, сложность коммуникации, обучение PAC и многие другие области исследований. Тем не менее, я не могу думать о каком-либо результате в TCS, который опирается на комплексный анализ (за...
Запутывание часто считается ключевым компонентом, который делает квантовые алгоритмы хорошо ... квантовыми, и это можно проследить до состояний Белла, которые разрушают идею квантовой физики как вероятностной модели скрытого состояния. В квантовой теории информации (из моего довольно слабого...
Чтобы проверить мое понимание, я хотел бы поделиться некоторыми мыслями об энергетических потребностях вычислений. Это продолжение моего предыдущего вопроса и может быть связано с вопросом Vinay о законах сохранения . Мне пришло в голову, что с термодинамической точки зрения выполнение вычислений...
Я читал « Является ли P против NP формально независимым? », Но я был озадачен. В теории сложности широко распространено мнение, что . Мой вопрос о том, что, если это не доказуемо (скажем, в ). (Предположим, что мы только узнаем, что не зависит от но никакой дополнительной информации о том, как это...
Я читал, что изначально Черч предложил -calculus как часть своей статьи «Постулаты логики» (которая читается плотно). Но Клини доказал свою «систему» непоследовательной, после чего Черч извлек соответствующие вещи для своей работы по «эффективной вычислимости» и отказался от своей предыдущей...
Я работал над внедрением некоторых результатов вычислительной сложности в теоретическую биологию, особенно эволюцию и экологию , с целью быть интересным / полезным для биологов. Одна из самых больших трудностей, с которыми я столкнулся, заключается в обосновании полезности асимптотического анализа...
В последнее время я начал изучать алгоритмы аппроксимации для NP-сложных задач и интересовался теоретическими причинами их изучения. (Вопрос не должен быть подстрекательским - мне просто любопытно). Из исследования алгоритмов аппроксимации возникла действительно прекрасная теория - связь между...
Мне интересно в широком смысле то, что известно о распараллеливании алгоритмов в P. Я нашел следующую статью в Википедии на эту тему: http://en.wikipedia.org/wiki/NC_%28complexity%29 Статья содержит следующее предложение: Неизвестно, является ли NC = P, но большинство исследователей подозревают,...
Обсуждение : В последнее время я проводил некоторое личное время, изучая различные вещи в сложности общения. Например, я повторно ознакомился с соответствующей главой в Арора / Барак, начал читать некоторые статьи и заказал книгу Кушилевица / Нисана. Интуитивно я хочу сравнить сложность...
В распределенных вычислениях проблема консенсуса, по-видимому, является одной из центральных тем, которая привлекла интенсивные исследования. В частности, статья «Невозможность распределенного консенсуса с одним ошибочным процессом» была удостоена награды PODC за выдающуюся работу в 2001 году . Так...