W jakim stopniu algorytm może przewidzieć złożoność czasową dowolnego programu wejściowego?

Powstrzymanie problemu twierdzi, że niemożliwe jest napisanie programu, który może określić, czy kolejne przystanków programowych dla wszystkich możliwych programów wejściowych .

Mogę jednak z pewnością napisać program, który może obliczyć czas działania programu takiego jak:

for(i=0; i<N; i++)
    { x = 1; }

i zwróć czasową złożoność , bez uruchamiania go. $N$

W przypadku wszystkich innych programów wejściowych zwracałby flagę wskazującą, że nie był w stanie określić złożoności czasowej.

Moje pytanie brzmi:

Jakie warunki musi spełnić, abyśmy mogli algorytmicznie określić złożoność czasową danego programu?

* Jeśli istnieje kanoniczne odniesienie lub artykuł przeglądowy, doceniłbym link do niego w komentarzach.

computability time-complexity formal-methods se.software-engineering Haczykowaty
źródło

(1) „Notacja O” nie oznacza „złożoności czasowej”. (2) Nie jest jasne, co rozumiesz przez „O (nieskończoność)”. Jeśli to możliwe, unikaj wymyślania nowej notacji. (3) Podejmowanie decyzji, czy dany program się zatrzymuje, czy nie, i określanie górnej granicy złożoności czasowej programu jest inne.

Tsuyoshi Ito,

Nie znam wnioskowania o złożoności czasowej programów w klasach ograniczonych, ale jedna klasa programów, którą warto sprawdzić, nazywa się „programami z pętlą ograniczoną”, dla których łatwo jest ograniczyć złożoność czasową. Pamiętam, że programy ograniczonej pętli są omówione w rozdziale 3 Gems of Theoretical Computer Science przez Uwe Schöninga i Randalla J. Pruima w kontekście decydowania o równoważności dwóch programów, ale nie jestem pewien, jak bardzo ten rozdział jest odpowiedni dla twojego pytania.

Tsuyoshi Ito,

Jestem trochę zmieszany. W jaki sposób jest to poza zakresem? Jedną rozsądną odpowiedzią na pytanie PO byłyby fragmenty języka (lub nawet klasy fragmentów), dla których czas działania można ustalić algorytmicznie.

Suresh Venkat

Powiązane pytanie: Czy granice środowiska wykonawczego w P są rozstrzygalne?

Artem Kaznatcheev

Strasznie spóźniłem się na ten komentarz. Wydaje się, że rzucamy się w momencie, gdy post pachnie nowicjuszem. Nie wskazuję palcami. Sam odczuwam ten instynkt. Może powinniśmy być łagodniejsi. PO przyznał się do nieznajomości obszaru lub warunków. Jaki jest sens witryny z pytaniami i odpowiedziami, jeśli tolerujemy tylko osoby, które dokładnie wiedzą, czego chcą i pytają w naszym języku.

Vijay D,

Odpowiedzi:

Zasadniczo nie można określić złożoności, nawet w przypadku zatrzymania programów: niech będzie dowolną maszyną Turinga i niech będzie programem (który zawsze zwraca 0): $T$ $p_T$

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

Oczywiste jest, że ogólnie nie można czy jest czasem liniowym, czy kwadratowym. $p_T$

Przeprowadzono jednak wiele pracy nad skutecznym obliczeniem złożoności programu. Szczególnie podoba mi się teoria niejawnej złożoności, która ma na celu tworzenie języków, które za pomocą specjalnych konstrukcji lub dyscyplin typów pozwalają pisać tylko programy, które zamieszkują określoną, ściśle określoną klasę złożoności. Według tego, co uważam za cud, języki te są często kompletne dla tej klasy!

Jeden szczególnie ładny przykład został opisany w tym artykule przez J.-Y. Marion, który opisuje drobny język imperatyw, z dyscypliny typu inspirowane z technik informacyjno-przepływowych i analiza zabezpieczeń, który umożliwia charakterystykę algorytmów w P .

cody
źródło

Na marginesie, zobacz także Epigram, który jest językiem, który może zagwarantować zakończenie.

Realz Slaw,

To dobry początek, ale czy jest coś więcej do powiedzenia? (Na przykład wydaje mi się, że środowisko wykonawcze danej elementarnej funkcji rekurencyjnej musi być łatwe do obliczenia, ale takie funkcje mogą rozwiązać każdy problem w hierarchii wykładniczej ....)

O ile możliwe jest ustalenie, że program wejściowy jest napisany w języku ograniczonym, można założyć, że złożoność czasowa jest ograniczona przez jakąkolwiek górną granicę narzuconą przez ten język. Jednak wiele prymitywnych funkcji rekurencyjnych ma ogólne równoważniki rekurencyjne, które są bardziej wydajne

Chris Pressey

(przypadkowo zapisał ten komentarz wcześniej, a następnie przekroczył limit 5 minut. Drugie zdanie powinno brzmieć następująco :) Jednak programy w tych ograniczonych językach mogą mieć odpowiedniki w mniej ograniczonych językach, które są bardziej wydajne (w szczególności wiele prymitywnych funkcji rekurencyjnych ma ogólne rekurencyjne odpowiedniki, które są bardziej wydajne), co w praktyce zachęca do korzystania z nieograniczonych, trudniejszych do analizy języków.

Chris Pressey,

To bardzo interesujące Chris! Czy masz referencje? W rzeczywistości wydaje się, że jest przeciwny do wniosku: podejrzewałbym, że prymitywne funkcje rekurencyjne mogą symulować ogólne funkcje rekurencyjne dla określonej liczby kroków, co ograniczyłoby wówczas przyspieszenie do pewnego stałego współczynnika.

cody,

Pytanie, które stawiasz i konkretna sztuczka liczenia, którą opisujesz, jest klasyczna w analizie programu. Istnieje teoretyczny problem analizy złożoności, a jego praktyczny przejaw polega na automatycznym szacowaniu wydajności fragmentu kodu. Taka zautomatyzowana analiza ma kilka aplikacji, od wykrywania błędów wydajności po szacowanie kosztów niektórych obliczeń w chmurze.

Cody wskazał, że problem jest ogólnie nierozstrzygalny. Ten problem jest trudniejszy niż udowodnienie zakończenia, ponieważ uzyskanie złożoności wiąże się z tym, że program również się kończy. Istnieją dwa podejścia do takiego problemu. Jeden pochodzi z analizy programu. Pomysł dodania licznika i oszacowania jego wartości istnieje od lat 70. XX wieku. To kodowanie zmniejsza problem określania czasu działania do obliczania niezmiennika.

Drugim podejściem jest zaprojektowanie języka programowania, który dopuszcza tylko programy o określonej ograniczonej złożoności. Jest to obszar niejawnej złożoności obliczeniowej.

Poniżej podano odniesienia do obu obszarów.

Projekt SPEED to jedna konkretna linia prac związanych z analizą programu, która koncentruje się na tym, jak znaleźć granice liczników po wprowadzeniu do programu. Liczniki mogą mierzyć zużycie czasu lub miejsca.
Wielowymiarowa amortyzowana analiza zasobów , Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012
Amir Ben Amram, w sprawie decydujących właściwości wzrostu programów imperatywnych , Rozwój w domniemanej kompilacji obliczeniowej 2010. Jest to piękna linia pracy nad ograniczaniem złożoności programów imperatywnych przez ograniczenia syntaktyczne.

Vijay D.
źródło