Besonderhede van voorbeeld: 7687877332710426868

German

Eine beschränkte Reduzierbarkeit ist eine Quasiordnung auf den Teilmengen natürlicher Zahlen, die man durch Einschränkung der Turing-Reduzierbarkeit erhält, indem man zusätzlich verlangt, dass für eine Reduktion von A auf B bei Eingabe x nur Anfragen y < f(x)+1 an das Orakel B gestellt werden dürfen, wobei f aus einer vorgegebenen Menge F total berechenbarer Funktionen stammt.

English

A bounded reducibility is a preorder on the power set of the integers which is obtained from Turing reducibility by the additional requirement that, for a reduction of A to B, for every input x the oracle B is only asked oracle queries y < f(x)+1, where f is from some given set F of total computable functions.