4625
правок
Задача легко решаемая: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
Таким образом, класс <math>{\mathcal P}</math> содержит только легко разрешимые задачи, а задачи, выходящие за класс <math>{\mathcal NP}</math>, являются труднорешаемыми. | Таким образом, класс <math>{\mathcal P}</math> содержит только легко разрешимые задачи, а задачи, выходящие за класс <math>{\mathcal NP}</math>, являются труднорешаемыми. | ||
Хотя классы <math>{\mathcal P}</math> и <math>{\mathcal NP}</math> были определены в терминах [[машина Тьюринга|машин Тьюринга]], можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую ''машину с произвольным доступом к памяти (равнодоступную адресную машину'' или ''РАМ''), которая является достаточно хорошим приближением к классу обычных, | Хотя [[классы P и NP|классы <math>{\mathcal P}</math> и <math>{\mathcal NP}</math>]] были определены в терминах [[машина Тьюринга|машин Тьюринга]], можно было бы использовать любую из многих других моделей вычислений, в том числе и так называемую ''машину с произвольным доступом к памяти (равнодоступную адресную машину'' или ''РАМ''), которая является достаточно хорошим приближением к классу обычных, | ||
традиционных вычислительных машин с точки зрения представления данных и алгоритмов, целиком помещающихся в оперативной памяти и имеющих дело с элементарными значениями, длины двоичных представлений которых ограничены некоторой константой. | традиционных вычислительных машин с точки зрения представления данных и алгоритмов, целиком помещающихся в оперативной памяти и имеющих дело с элементарными значениями, длины двоичных представлений которых ограничены некоторой константой. | ||