Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?” lub „Czy 2 lg ∗ x ∈ O ( lg lg x ) ?”.
Jeśli ograniczymy funkcje do wielomianów (wyrażonych w zwykły sposób), nie będzie to trudne. Zobacz także normalną formę Cantor .
Jak duże możemy uczynić klasę funkcji, zanim porównanie stanie się nierozstrzygalne? Czy możemy rozszerzyć go na funkcje używane w typowej klasie algorytmów licencjackich?
Jak wyjaśnia Joshua Grochow w komentarzach, naprawdę interesuje mnie zestaw wyrażeń, a nie same funkcje. Tak więc, na przykład, byłbym zainteresowany procedurami decyzyjnymi, które mogłyby porównywać „ ” i „ 2 ”, nawet jeśli nie mogą porównać „ ln e ” i „ n ( ln n ) - 1 ”.
Ewentualnie powiązane pytanie: „Czy teoria granic asymptotycznych jest całkowicie aksjomatyczna?”
źródło
Odpowiedzi:
Boshernitzan rozszerzył tę klasę jeszcze bardziej i bez wątpienia istnieją inne prace na ten temat.
źródło