КАТЕГОРИЯ
Теория вычислений
21 материалов
Тезис Чёрча-ТьюрингаЭффективно вычислимые функции вычислимы машиной Тьюринга.Теорема Кука-ЛевинаSAT является NP-полной задачей.NP-полнотаРешение одной NP-полной задачи эффективно решило бы все задачи NP.PSPACE-полнотаНекоторые задачи требуют полиномиальной памяти и потенциально экспоненциального времени.Теорема об иерархии времениДополнительное вычислительное время строго увеличивает класс решаемых задач.Теорема об иерархии памятиДополнительная память строго увеличивает вычислительные возможности.Диагональный аргумент КантораНекоторые бесконечности строго больше других.Busy BeaverМаксимальное время остановки маленькой машины растет быстрее любой вычислимой функции.Лемма о накачкеНеобходимое свойство помогает доказывать нерегулярность языков.Иерархия ХомскогоГрамматики различаются выразительной силой и вычислительными ограничениями.Теорема Блума об ускоренииДля некоторых задач не существует асимптотически лучшего алгоритма.No Free LunchБез предположений о задачах ни один оптимизатор не лучше другого в среднем.Теорема невозможности полного статического анализаПолный точный анализ поведения произвольных программ невозможен.Böhm–Jacopini TheoremЛюбой алгоритм выражается последовательностью, выбором и циклом.Curry–Howard CorrespondenceТипы соответствуют утверждениям, программы - доказательствам.CAP как теорема невозможностиРазделение сети вынуждает отказаться от доступности или линейной согласованности.Проблема P против NPСпрашивает, совпадает ли класс быстро проверяемых задач с быстро решаемыми.Полиномиальная сводимостьПереносит решение одной задачи к другой с полиномиальными затратами.Пространственная сложностьИзмеряет объем памяти, необходимый алгоритму.Временная сложностьИзмеряет рост числа операций с размером входа.Теорема Чёрча-РоссераГарантирует единственность нормальной формы в конфлюэнтном лямбда-исчислении.