Вопросы с тегом «physics»

42
Физика результатов в ТКС?

Кажется очевидным, что результаты теоретической физики значительно повлияли на ряд подполей теоретической информатики. Два примера этого Квантовые вычисления Результаты статистической механики, используемые в анализе сложности / эвристических алгоритмах. Итак, мой вопрос: есть ли какие-то основные...

35
Формальное понятие для энергетической сложности вычислительных задач

Вычислительная сложность включает в себя изучение временной или пространственной сложности вычислительных задач. С точки зрения мобильных вычислений энергия является очень ценным вычислительным ресурсом. Итак, есть ли хорошо изученная адаптация машин Тьюринга, учитывающая энергию, потребляемую при...

33
Что такое объем информации?

Этот вопрос был задан Жанетт Уинг после ее презентации PCAST по информатике. «С точки зрения физики, есть ли максимальный объем информации, который мы можем иметь?» (Хороший вопрос для теоретического сообщества информатики, так как я думаю, что возникает вопрос «Что такое информация?») За пределами...

33
Последствия

Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор: Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время. «Квантовой магии будет недостаточно» (Беннетт и...

30
Должны ли мы считать

Многие эксперты считают, что гипотеза верна, и используют ее в своих результатах. Меня беспокоит то, что сложность сильно зависит от гипотезы P ≠ N P.PNPP≠NP\mathsf{P} \neq \mathsf{NP}PNPP≠NP\mathsf{P} \neq \mathsf{NP} Итак, мой вопрос: Пока гипотеза не доказана, можно / нужно ли рассматривать ее...

29
Что подразумевается под аргументами эвристической статистической физики?

Я слышал, что в статистической физике есть эвристические аргументы, которые дают результаты в теории вероятностей, для которых строгие доказательства либо неизвестны, либо очень трудно получить. Что является простым игрушечным примером такого явления? Было бы хорошо, если бы ответ предполагал...

22
Энергетические соображения при расчете

Чтобы проверить мое понимание, я хотел бы поделиться некоторыми мыслями об энергетических потребностях вычислений. Это продолжение моего предыдущего вопроса и может быть связано с вопросом Vinay о законах сохранения . Мне пришло в голову, что с термодинамической точки зрения выполнение вычислений...

22
Сколько вычислительной мощности умещается в кубический сантиметр?

Этот вопрос является продолжением вопроса об алгоритмах ДНК, заданного Аадитой Мехра . В комментариях Джо Фитцсиммонс сказал, частично: [T] Радиус системы должен масштабироваться пропорционально массе, чтобы избежать этого. Вычислительная мощность масштабируется максимально линейно по массе. Таким...

22
Точный плоский электрический поток

Рассмотрим электрическую сеть, смоделированную как планарный граф G, где каждое ребро представляет собой резистор 1 Ом. Как быстро мы можем вычислить точное эффективное сопротивление между двумя вершинами в G? Эквивалентно, как быстро мы можем вычислить точный ток, протекающий вдоль каждого края,...

19
Есть ли у криптографии термодинамические затраты?

Обратимые вычисления - это вычислительная модель, которая допускает только термодинамически обратимые операции. В соответствии с принципом Ландауэра, который гласит, что стирание небольшого количества информации высвобождает джоулей тепла, это исключает переходные функции, которые не являются...

19
Существует ли геометрическая картина для адиабатических квантовых вычислений?

В адиабатических квантовых вычислениях (AQC) каждый кодирует решение задачи оптимизации в основном состоянии [проблемы] гамильтониана . Чтобы добраться до этого основного состояния, вы начинаете в легко охлаждаемом начальном (основном) состоянии с гамильтонианом и «отжигом» (адиабатически...

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

16
Есть ли название для «физических вещей, из которых можно построить машину Тьюринга»?

Одна из удивительных вещей в компьютерной науке заключается в том, что физическая реализация в некотором смысле «неактуальна». Люди успешно создали компьютеры из нескольких различных подложек - реле, вакуумных трубок, дискретных транзисторов и т. Д. Вскоре люди могут преуспеть в создании...

12
Энтропия и вычислительная сложность

Есть исследователь, показывающий, что стирающий бит должен потреблять энергию, а сейчас проводится какое-либо исследование среднего потребления энергии алгоритмом с вычислительной сложностью ? Я предполагаю, что вычислительная сложность F ( n ) коррелирует со средним потреблением энергии, надеюсь,...

11
Как выглядят осязаемые Квантовые Врата?

Я читал опубликованные книги, статьи и статьи о квантовых вычислениях. Я обнаружил, что все материалы, которые я видел, вместо того, чтобы описывать квантовые врата от базовой физики до абстракции, изо всех сил стараются не говорить о деталях реализации квантовых ворот . Сначала я задал себе...

10
Практические последствия

Фон Сложность схемы определяется как набор семейств схем (т. Е. Последовательности схем, по одной для каждого входного размера) ограниченной глубины и полиномиального размера, построенных с использованием неограниченного разветвления И, ИЛИ и НЕ.A C0AC0AC^0 Функция четности с n- битным входом равна...

10
Сведение трудных задач к физическим моделям

Я ищу примеры сложных проблем (в NP или более сложных) из информатики, которые могут быть сведены к моделям физических процессов. Например, max-2-sat может быть сведен к минимизации энергии в модели Изинга. Я хотел бы найти больше примеров такого типа...

10
Квантовые алгоритмы для расчетов КЭД, связанные с константами тонкой структуры

Мой вопрос касается квантовых алгоритмов для расчетов КЭД (квантовой электродинамики), связанных с константами тонкой структуры. Такие вычисления (как мне объяснили) равносильны вычислению рядов, подобных Тейлору где - постоянная тонкой структуры (около 1/137), а - вклад диаграмм Фейнмана с...

9
Естественное вычисление, основанное на фундаментальных силах

Хорошо известными примерами вычислений, вдохновленных природными явлениями, являются квантовые компьютеры и компьютеры с ДНК. Что известно о потенциале и / или ограничениях вычислений по законам Максвелла или гравитации? То есть непосредственное включение природных «быстрых» решений уравнений...