Я просто читаю лямбда-исчисление, чтобы «узнать это». Я рассматриваю это как альтернативную форму вычислений в отличие от машины Тьюринга. Это интересный способ работы с функциями / сокращениями (грубо говоря). Некоторые вопросы продолжают мучить меня, хотя: Какой смысл в лямбда-исчислении? Зачем...
Извините за запоминающееся название. Я хочу понять, что нужно сделать, чтобы опровергнуть тезис Черча-Тьюринга? Где-то я читал, что это математически невозможно сделать! Почему? Тьюринг, Россер и т. Д. Использовали разные термины, чтобы различать: «что можно вычислить» и «что можно вычислить с...
Какая самая смешная опубликованная работа, связанная с TCS, вы знаете? Пожалуйста, включайте только те, которые предназначены для забавы. Работы, которые явно созданы для того, чтобы быть разумно юмористическими (а не, скажем, опубликованным сборником коротких анекдотов о теории сложности),...
Это «исторический вопрос» больше, чем вопрос исследования, но было ли классическое сведение к нахождению порядка в алгоритме факторизации Шора первоначально обнаруженным Питером Шором, или это было известно ранее? Есть ли статья, описывающая сокращение, предшествующее Шору, или это просто так...
В настоящее время я студент бакалавриата, который должен закончить в этом году. После выпуска я планирую работать в магистратуре / докторантуре TCS. Я начал задаваться вопросом, какие области математики считаются полезными для TCS, особенно (классическая) теория сложности. Какие области вы считаете...
В свете анонса первого в мире программируемого квантово-фотонного чипа мне стало интересно, каким будет программное обеспечение для компьютера, использующего квантовую запутанность. Одна из первых программ, которые я когда-либо писал for i = 1 to 10 print i next i Кто-нибудь может привести пример...
Этот вопрос может не подходить здесь, но я не мог найти лучшее место, чтобы спросить (это было закрыто в SO). Я нахожу труды для изучения компьютерных наук трудными для понимания. Конечно предметы сложные. Но после того, как я понимаю статью, обычно я могу сказать ее кому-то более простым языком и...
Пожалуйста, перечислите примеры, где теорема из математики, которая обычно не считалась применимой в информатике, была впервые использована для доказательства результата в информатике. Лучшими примерами являются те, где связь не была очевидной, но как только она была обнаружена, это, безусловно,...
В ответе на предыдущий вопрос я упомянул распространенное, но ошибочное мнение, что «гауссовское» исключение происходит за времени. Хотя очевидно, что алгоритм использует O ( n 3 ) арифметических операций, небрежная реализация может создавать числа с экспоненциально большим количеством битов. В...
Иногда математики беспокоятся об аксиоме выбора (AC) и аксиоме детерминированности (AD). Аксиома выбора : При любом наборе непустых множеств существует функция F , что, учитывая множество S в C , возвращает элемент из S .СC{\cal C}еffSSSСC{\cal C}SSS Аксиома детерминированности : Пусть - набор...
Я практикующий программист, и я пишу обзор алгебраических структур для личного исследования и пытаюсь привести примеры того, как эти структуры используются в теоретической информатике (и, в меньшей степени, в других областях компьютерных наук). , В рамках теории групп я встречал синтаксические...
Какие алгоритмы законной полезности просто слишком сложны для реализации? Позвольте мне прояснить: я не ищу алгоритмы, такие как текущий асимптотический алгоритм оптимального умножения матриц (Coppersmith-Winograd), который разумно реализовать, но имеет константу, которая делает его бесполезным на...
Исходя из более математического фона, я так и не научился писать код. Я начинаю докторскую диссертацию в TCS, и многие были удивлены тем, как мало я знал о программировании (и о компьютере в целом). Я могу писать алгоритмы в псевдокоде, но я не знаю языка программирования. Я могу себе представить,...
В настоящее время решается либо полная проблема, либоP S P A C ENPNпNPPSPACЕпSпAСЕPSPACE complete в общем случае невозможно для больших входов. Однако оба они разрешимы в экспоненциальном времени и в полиномиальном пространстве. Поскольку мы не можем создавать недетерминированные или «счастливые»...
Я знаком со многими результатами, в которых используется теорема PCP (главным образом в приближенных алгоритмах), но я никогда не сталкивался с четким объяснением теоремы PCP (то есть, что ).N P = P C P (O(log( н ) ) , O ( 1 ) )Nпзнак равнопСп(О(журнал(N)),О(1))\mathsf{NP} =...
Заданный вопрос состоит в том, является ли следующий вопрос разрешимым: Проблема Учитывая целое число kkk и обещанная машина Тьюринга MMM в P, является ли время выполнения MMM O(nk)O(nk){O}(n^k) относительно длины ввода nnn ? Узкий ответ «да», «нет» или «открытый» является приемлемым (со...
Недавний вопрос по Гека Bennett с просьбой , был ли класс PH содержится в классе РР, получил несколько противоречивые ответы (все это правда, кажется). С одной стороны, несколько результатов оракула были даны наоборот, а с другой Скотт предположил, что ответ, вероятно, положительный, так как...
РЕДАКТИРОВАТЬ НА 10/12/08: Я постараюсь изменить вопрос, чтобы он мог заинтересовать больше людей поделиться своим мнением. Нам нужен ваш вклад! Этот пост вдохновлен тем, что в МО: Примеры распространенных ложных убеждений в математике . Большие списки иногда генерируют огромное количество ответов,...
Обновлено ниже Мы все знаем о критической важности рецензирования. Это основная форма контроля качества и обратной связи по исследованиям. Однако, для исследователя ранней стадии (такого как я) иногда это может быть запутанной системой / процессом. Соответственно, есть несколько трактатов по...
Мой вопрос сегодня (как обычно) немного глупый; но я бы попросил вас рассмотреть это. Я хотел знать о происхождении и / или мотивации концепции ширины дерева. Я уверен, что понимаю, что это используется в алгоритмах FPT, но я не думаю, что это было причиной, почему это понятие было определено. Я...