Kto wprowadził niedeterministyczne obliczenia?

Mam dwa historyczne pytania:

Kto pierwszy opisał obliczenia niedeterministyczne?

Wiem, że Cook opisał problemy z NP-zupełnością i że Edmonds zaproponował, że algorytmy P są algorytmami „wydajnymi” lub „dobrymi”.

Przeszukałem ten artykuł w Wikipedii i odszukałem „O złożoności obliczeniowej algorytmów”, ale nie mogłem znaleźć żadnego odniesienia do pierwszego omówienia obliczeń niedeterministycznych.

Jakie było pierwsze odniesienie do klasy NP? Czy to był papier Cooka z 1971 roku?

— Philip White
źródło

NP został również wynaleziony mniej więcej jednocześnie przez Levina po drugiej stronie żelaznej kurtyny. Oprócz Edmondsa, Rabin i Cobham (każdy z osobna) również „wprowadzili” P, chociaż Edmonds był chyba najbardziej skuteczny w uzasadnieniu punktu widzenia P jako „wydajnego”.

— Joshua Grochow

Papier Karps 1972 jest uważany za kluczowy kontrapunkt w stosunku do dokumentu Cooksa, który pokazuje, że wiele problemów jest NP kompletnych; w pewnym sensie Cook pokazał tylko, że SAT był NP kompletny i po tym artykule nie było oczywiste, jak obejmująca może być ta koncepcja.

— vzn

(krótka myśl), więc dwa artykuły Cook / Karp były jak „1-2 uderzenie” w społeczność / zbiorowe zrozumienie TCS. także w przypadku takich historycznych pytań czasami koncepcje są „w powietrzu” i nie ma jednej unikalnej / ostatecznej odpowiedzi, ale kilka prawie równie wykonalnych odpowiedzi. Innym miejscem do obejrzenia jest artykuł Turingsa z 1936 r. na temat TM, nigdy nie widziałem, aby ktokolwiek analizował / dekonstruował jednoznacznie, że nic w długim artykule nie jest zbliżone do niedeterminizmu.

— vzn

jeszcze inny punkt widzenia (w tym złożonym / wielowymiarowym temacie): paralelizm ma wiele podobieństw do niedeterminizmu.

— vzn

Warto również zauważyć, że Godel uznał znaczenie złożoności i prawdopodobnie przewidział P jako algorytmy „wydajne”. rjlipton.wordpress.com/the-gdel-letter

— evanb

Odpowiedzi:

Zawsze widziałem w obliczeniach pojęcie niedeterminizmu przypisywane Michaelowi Rabinowi i Danie Scott. Zdefiniowali niedeterministyczne automaty skończone w swoim słynnym artykule Finite Automata i ich problemy decyzyjne , 1959. Przywołanie nagrody Rabina Turinga sugeruje również, że Rabin i Scott wprowadzili maszyny niedeterministyczne.

— Sasho Nikolov
źródło

Oto, co Odifreddi mówi na ten temat:

„Nasz model maszyny Turinga jest deterministyczny, w tym sensie, że instrukcje muszą być spójne (co najwyżej jedno z nich ma zastosowanie w danej sytuacji). Elementy losowe w urządzeniach obliczeniowych zostały wprowadzone wcześnie przez Shannona [1948] i De Leeuw, Moore, Shannon i Shapiro [1956]. Istnieją zasadniczo dwa modele. Niedeterministyczne maszyny Turinga zachowują się w niejednoznacznej sytuacji, w której mogą być stosowane sprzeczne instrukcje, wybierając losowo jeden z nich: ich moc obliczeniowa, przynajmniej dla 0, Funkcje (zbiory) o wartości 1 nie przekraczają mocy tych deterministycznych. Maszyny probabilistyczne różnią się od niedeterministycznych tym, że prawdopodobieństwo następnego stanu jest prawdopodobne, a zatem sprzeczne instrukcje nie mają takiej samej szansy na wybranie przez maszynę. ”
[P. Odifreddi, Klasyczna teoria rekurencji, t. 1, strona 50]

Należy zauważyć, że pojęcie nondeterminism w sensie „istnieje + weryfikator” istniała teoria obliczalności długo przed teorii złożoności, np postaci normalnej KLEENE za , hierarchii arytmetycznej . Inne modele obliczeń, takie jak systemy kanoniczne Post (znane przynajmniej od 1943 r.) I gramatyki, również nie są deterministyczne. Myślę, że można nawet przesunąć pojęcie do czasów rachunku epsilon i operatorów wyboru Hilberta .

O NP zapytałem Steve'a Cooka. Nazwę NP dla klasy niedeterministycznych problemów obliczeniowych w czasie wielomianowym wprowadził Richard Karp w swoim słynnym artykule z 1972 roku. Cook odnosi się do klasy niedeterministycznych problemów obliczeniowych maszyny Turinga w wielomianowym czasie w swoim słynnym artykule z 1971 r., Który określa wielomianowe skrócenie czasu i pokazuje, że istnieją całkowite problemy, ale bez podania nazwy tej klasie.

Przed jego pracą nie było dużego zainteresowania problemami obliczalnymi w czasie wielomianowym przez niedeterministyczne maszyny Turinga, dopiero po pracy Karpa stało się jasne, że tak wiele naturalnych problemów dotyczy NP. Po pracy Cooka niektórzy zainteresowali się, szczególnie dwie, które zainteresowały się wcześnie (zanim ukazał się artykuł Karpa) to Michael Rabin i Allan Borodin .

Artykuł Karpa z 1972 roku zaskoczył ludzi, pokazując, jak wszechobecna jest zupełna NP wśród naturalnych problemów.

— Kaveh
źródło

Używanie terminu „losowy” w tym kontekście jest niebezpieczne, nie odnosi się do losowości w sensie statystycznym, a jedynie fakt, że wybór pozostaje pusty.

— reinierpost

@reinierpost, tak, to mylące, że twierdzi, że niedeterministyczna maszyna wybiera losowo następny stan (ale w każdym razie sama niedeterministyczna maszyna sama się myli, dlatego ludzie zazwyczaj wolą weryfikacyjną definicję NP).

— Kaveh

Nigdy nie uważałem tego za mylące. Może jestem tak zagubiony, że nie zdaję sobie z tego sprawy.

— reinierpost

Rabin i Scott przedstawili niedeterministyczne automaty skończone w swoim artykule badawczym opublikowanym w czasopiśmie IBM, kwiecień 1959 r. W artykule wspomniano:

przyjęliśmy jeszcze prostszą formę definicji, rezygnując ze skomplikowanej funkcji wyjściowej, a nasze maszyny po prostu dają odpowiedzi „tak” lub „nie”. Tego używał również Myhill, ale nasze uogólnienia na maszyny „niedeterministyczne”, „dwukierunkowe” i „wielopasmowe” wydają się być nowe .

Cały artykuł można zobaczyć tutaj: http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf

— użytkownik35319
źródło