Русская Википедия:Эффективный процесс

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Пусть задано некоторое множество <math>M</math>, часть элементов которого обладает свойством <math>U</math>. Тогда эффективным процессом (методом, алгоритмом) называется такой процесс, который для любого элемента <math>x \in M</math>позволяет за конечное число шагов выяснить, обладает ли элемент <math>x</math> свойством <math>U</math> или не обладает.

Полуэффективный процесс

Если элемент <math>x</math> обладает свойством <math>U</math>, полуэффективный процесс позволяет это выявить за конечное число шагов. Если же <math>x</math> не обладает свойством <math>U</math>, полуэффективный процесс, возможно, не сможет сказать ничего определенного об <math>x</math> за конечное число шагов.

Таким образом, с помощью полуэффективного процесса мы либо узнаем, что <math>x</math> обладает свойством <math>U</math>, либо не сможем ничего выяснить в отношении <math>x</math>.

См. также


Шаблон:Rq