W uczeniu obliczeniowym twierdzenie NFL stwierdza, że nie ma uniwersalnego ucznia. Dla każdego algorytmu uczenia się istnieje rozkład, który powoduje, że uczeń wysyła hipotezę z dużym błędem, z dużym prawdopodobieństwem (choć istnieje hipoteza o niskim błędzie). Wniosek jest taki, że aby się uczyć, klasa hipotez lub dystrybucje muszą być ograniczone. W swojej książce „Probabilistyczna teoria rozpoznawania wzorów” Devroye i wsp. Udowodnili następującą tezę dla ucznia z najbliższych sąsiadów:
Gdzie