Reducere (teoria complexității computaționale)
Reducerea teoriei complexității computaționale este transformarea unei probleme în alta. În general, pentru un algoritm care convertește instanțe ale unei probleme în instanțe ale unei probleme care au același răspuns ("da" sau "nu"), se spune că se reduce la , deci reductibilitatea este relația dintre două probleme. Cu ajutorul unei astfel de conexiuni se poate dovedi calculabilitatea problemei sau apartenența acesteia la una sau la alta clasă de complexitate .
Unele tipuri de informații: Reducere Cooke , Reducere Karp , Reducere Levin , Reducere Turing . Reducerea Turing este cea mai generală formă de reducere: un algoritm (calculabil pe o mașină Turing ) poate fi apelat de orice număr de ori, iar fiecare apel va fi considerat ca un pas al algoritmului; pentru a defini formal reductibilitatea Turing, se folosește conceptul de mașină Turing cu un oracol .
Literatură
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M .: „Williams” , 2002. - S. 528. - ISBN 0-201-44124-1 .