No dobrze, można by powiedzieć, ale przecież zazwyczaj mamy doczynienia z obiektami, a więc i łańcuchami skończonymi. Cantorowska teoria mnogości jest niewątpliwie fascynująca matematycznie ale w realnym życiu nikt nam (niestety) nie przyzna grantu na obserwowanie deszczu za oknem choćby przez dziesięć lat. Dlatego wypada rozważyć przypadek łańcuchów binarnych skończonych. Powiedzmy o długości n. Rzecz jasna wszystkich ich jest 2^n czyli policzalnie skończenie wiele. Skoro łańcuchy i ich liczba są skończone to dla każdego istnieje też skończona "teoria" czyli każdy może być skompresowany do łańcucha także skończonej długości. Zachodzi jednak pytanie: jaki jest rozkład długości generatorów? Jak bardzo skończone łańcuchy dają się "ścisnąć"? Przyjmijmy, że dysponujemy "doskonałą" metodą kompresji uwalniającą nas od wszelkich technicznych trudności niełatwej sztuki bezstratnego skracania. Oczywiście chcielibyśmy aby łańcuchy skompresowane były jak najkrótsze. Najkrótsze w ogóle są łańcuchy: 0 i 1. Mają tę zaletę, że są bardzo krótkie i tę zasadniczą wadę, że są tylko dwa. Weźmy więc następne: 00,01,10,11. Niestety są tylko cztery a my potrzebujemy 2^n. Nietrudno zauważyć, że 2^n= 2^(n-1)+2^(n-2)+... ...+2^(n-n)+1. Wynika z tego, że połowę łańcuchów możemy skrócić o tylko jedno miejsce, jedną czwartą o dwa, a zdecydowaną większość tylko o kilka miejsc. Mówiąc prosto większość z nich możemy tylko opisać ponieważ ich złożoność obliczeniowa jest prawie równa ich długości. "Generator" czy "teoria" długa jak sm łańcuch jest właśnie opisem. Czasem tylko mamy szczęście zetknąć się z przypadkiem umożliwiającym sformułowanie "eleganckiej" teorii. Możliwe są zatem dwa błędy metodologiczne. Pierwszy to szukanie, postulowanie "eleganckiej" teorii na siłę, to znaczy tam, gdzie ze względu na własności przedmiotu nie jest ona możliwa. Drugi odwrotnie polega na zadowalaniu się opisami tam gdzie zgrabna, ogólna teoria jest możliwa. Czy jednak potrafimy ich uniknąć? Co może nam pomóc w określaniu złożoności? Spróbujemy przyjrzeć się dalej.
