Jaki jest przykład problemu biznesowego niemożliwego do obliczenia?

17

Mam współpracownika, który odmawia zaakceptowania rzeczywistości, w której maszyny Turinga (a także maszyny von Neumana) nie są w stanie rozwiązać własnego problemu zatrzymania, stwierdzając:

Możesz zrobić wszystko, mając wystarczająco dużo czasu i pieniędzy.

Nie lubi też problemów teoretycznych, argumentując, że:

W naszej dziedzinie nigdy nie napotkamy na te pytania. Jesteśmy twórcami aplikacji, a nie naukowcami teoretycznymi.

Czy istnieje dobry przykład problemu biznesowego, który jest obliczeniowo niemożliwy, którego mógłbym użyć, aby przekonać go o tym?

Jesan Fafon
źródło
11
Nie możesz pokazać na przykładzie, że coś jest niemożliwe. Twój współpracownik powie po prostu: „To nie działa, ponieważ nie opracowaliśmy właściwego podejścia”. Najlepsze, co możesz zrobić, to pokazać mu dowód. Jeśli tego nie kupi, jest naprawdę głupi, kretyn albo jedno i drugie. Oto lista nierozstrzygniętych problemów: en.wikipedia.org/wiki/List_of_undecidable_problems
Thomas Eding
18
Teoretykowi i inżynierowi powiedziano, że mogą pocałować dziewczynę, wielokrotnie podróżując między nimi a nią o połowę. Teoretyk natychmiast się poddał mówiąc: „to niemożliwe, nigdy się tam nie dostanę”. Inżynier poszedł po to, mówiąc: „Zbliżę się wystarczająco do celów praktycznych”. Proszę pana, proszę spróbować tego pocałunku.
gbjbaanb
2
@gbjbaanb: To dobry deskryptor wielu nieoptymalnych rozwiązań problemów NP-trudnych, a wiedza o tych problemach (praktycznie) niemożliwych do rozwiązania klasycznego jest powodem wyboru alternatywnej metody. Jeśli nie zaakceptujesz, że niektóre problemy są praktycznie lub dosłownie niemożliwe do rozwiązania, nie będziesz szukać niedoskonałych rozwiązań, które mogą dać „wystarczająco dobrą” odpowiedź po nieokreślonym czasie.
Phoshi
3
@ Phoshi nie, chodzi o to, że rzeczywiste rozwiązania inżynieryjne wymagają jedynie rozwiązania, które jest wystarczająco dobre, aby rozwiązać problem wystarczająco do zaakceptowania. Rozwiązanie go idealnie nie jest warte czasu i kosztów. na przykład. Problem sprzedawcy podróżującego jest niemożliwy, biorąc pod uwagę więcej niż kilka węzłów, ale wiele firm nie zawsze zapewnia optymalne rozwiązanie. Gdybyśmy tylko stworzyli doskonałość, nikt by jej nie miał.
gbjbaanb
10
@gbjbaanb: To prawda, ale jedynym powodem, dla którego rozwiązali te problemy, jest zaakceptowanie faktu, że nie można „nic zrobić z wystarczającą ilością czasu i pieniędzy”, i przestano szukać optymalnego rozwiązania. Wiedza czego nie może zrobić, to często tak samo ważne, aby znaleźć rozwiązanie jak znajomość co może zrobić.
Phoshi

Odpowiedzi:

11

Nie technicznie niemożliwe, ale ...

Planowanie zasobów w celu znalezienia idealnego harmonogramu maksymalizującego wykorzystanie przedziałów czasowych. Kiedyś, podczas moich wcześniejszych obliczeń, miałem projekt, który wymagał tego. Pracowałem nad tym przez jakiś czas, zanim zdałem sobie sprawę, że było to trudne dla NP.

Inne przykłady problemów, które nie są technicznie niemożliwe, ale są technicznie trudne, można znaleźć tutaj .

Większość trudnych problemów obliczeniowych w informatyce biznesowej nie jest niemożliwa, tylko niepraktyczna. Twój przyjaciel ma rację; możesz rozwiązać większość z nich, jeśli rzucisz na nie wystarczającą ilością pieniędzy. Ale argument jest podstępny; sednem prowadzenia firmy jest zarabianie pieniędzy, a nie ich tracenie.

W codziennej praktyce mówimy o kompletności Turinga w sposób niejasny, nie po to, by zademonstrować jakąś matematyczną zasadę, ale aby zilustrować (na przykład) nieadekwatność HTML i CSS jako kompletnego narzędzia do tworzenia programów z pełną funkcjonalnością.

Podobnie problem zatrzymania jest ważny dla teoretyków, ale nie ma większego znaczenia dla większości firm.

Robert Harvey
źródło
14
Problem zatrzymania pojawia się w statycznej analizie kodu. Z tego można uzyskać przyziemne problemy, takie jak „tutaj jest jakiś kod, spraw, by wyglądał ładnie”, aby „tutaj jest jakiś kod, czy to złośliwe oprogramowanie” - pierwszy z nich jest ważny dla firm tworzących IDE (podświetlanie składni, refaktoryzacja), drugi do firmy antywirusowe i specjaliści od bezpieczeństwa.
12
„Podobnie problem zatrzymania jest ważny dla teoretyków, ale nie ma większego znaczenia dla większości firm.”: Cóż, gdyby problem zatrzymania był obliczalny, moglibyśmy automatycznie sprawdzić, czy jakiś program się zakończy / zawiesi określony wkład czy nie. Prawdopodobnie nie mielibyśmy już żadnych BSOD. Ponieważ nie jest to możliwe, musimy zastosować inne techniki w celu zapewnienia jakości oprogramowania (takie jak testowanie) i nikt nie inwestuje czasu i pieniędzy, aby opracować ogólny program „sprawdzania zakończenia”. Myślę więc, że ten teoretyczny wynik ma ogromne znaczenie praktyczne.
Giorgio
4

Inni skomentowali to, ale spróbuję napisać odpowiedź, podając mój punkt widzenia.

Podoba mi się odpowiedź Roberta Harveya i komentarze do jego odpowiedzi, i chciałbym rozwinąć je.

Myślę, że musisz przedstawić te nierozstrzygalne problemy (takie jak zakończenie) w przyziemny sposób: na przykład narzędzie IDE, które „sprawdza, czy ta funkcja zawsze zwraca wartość”.

Podczas nauczania moim ulubionym przykładem było refaktoryzacja ( równoważność funkcji, kolejny nierozstrzygalny problem ). Zapytałam:

Jak sprawdzisz, czy funkcja / program robi to samo po ładnym refaktoryzacji? Oczywiście, mamy na to testy jednostkowe, ale nie obejmują one wszystkich przypadków. I nudzą się pisać ... Ale jesteśmy programistami! Powinniśmy napisać program, który sprawdza, czy te dwie funkcje dają zawsze ten sam wynik! Dlaczego nie spróbujesz tego napisać?

lub, jako wariant może być bliżej twojej sprawy:

Mamy ten starszy kod napisany w starożytnym, niejasnym dialekcie COBOL, dla którego nie ma specyfikacji ani kompilatora. Mamy tylko program. Cała nasza działalność na tym polega, dlatego musimy być w 100% pewni, że nowy kod Java robi dokładnie to samo w każdej sytuacji. Kierownictwo chce programu, który to robi, sprawdzając wszystkie możliwe przypadki i szacuje, że można to zrobić w ciągu 6 do 8 tygodni. Dlaczego nie spróbujesz tego napisać?

Nie chodzi o to, żeby napisać taki program. Lub wystarczająco dobre przybliżenie wymagań. Chodzi o to, aby uświadomić sobie, że NIE można tego zrobić bezpośrednio, NIE marnuj niezliczonej ilości naszych, próbując wymyślić, jak to zrobić (tylko aby uświadomić sobie, że nie jest to możliwe), ale rozpoznaj to. „Ach! To nierozstrzygalne! Nie można tego zrobić bezpośrednio. Muszę wymyślić inny, bardziej sprytny sposób, z wystarczającym przybliżeniem”.

Musisz wymyślić sposób przedstawienia problemu w rozpoznawalny i pozornie prosty sposób. Nie uwierzyłbyś, ilu studentów CS spróbuje napisać taki program od razu ... przed przystąpieniem do klasy obliczeniowej :)

Lorenzo Dematté
źródło
Drugi cytat próbuje nieprawidłowo wywołać problem zatrzymania; jednak jeśli wiemy, że program COBOL działa i możemy go uruchomić w środowisku testowym (w razie potrzeby sklonuj vm-PROD), problem zatrzymania jest wykluczony i możemy spróbować. Prawdopodobnie ręcznie, a nie programowo, ale i tak możemy to zrobić. W razie potrzeby możemy podzielić wszystkie możliwe formy wprowadzania danych na drzewa. Ponieważ program docelowy zatrzymuje się, drzewo dzieli się na dwie części.
Joshua
2

Zakładając, że na razie możemy odłożyć na bok pytania moralne:

Firma A zawarła z tobą umowę na sposób komunikacji między biurami satelitarnymi A1 i A2, przy czym nikt poza osobami upoważnionymi w A1 i A2 nie jest w stanie zrozumieć komunikacji.

Firma B zawarła z tobą umowę na sposób inteligentnego podsłuchiwania wszelkiej komunikacji między A1 i A2.

Oczywiście nie możesz zrobić obu.

Ze względu na sposób działania matematyki (dokładna matematyka jest przedmiotem ciągłych badań od 100 lat) nie można spełnić jednego z następujących wymagań:

(1): Podaj algorytm szyfrowania, którego atakujący nie może złamać, mając do dyspozycji dowolną ilość pieniędzy.

(2): Zapewnij algorytm łamania szyfru dla dowolnego algorytmu szyfrowania, który działa w rozsądnym czasie.

Jozuego
źródło
1
(3): Nie udało się znaleźć innej pracy po tym, jak rynek dowiaduje się, że nawet próbowałeś obu
TruthOf42,
1

Ostatnio wziąłem udział w zajęciach na temat modelu i notacji biznesowej ( BPMN ). Łatwo zauważyć, że przepływy pracy z wieloma zbyt podziałami, złączeniami i pętlami stają się szybko niepraktyczne (choć niekoniecznie niemożliwe , AFAIK) do zrozumienia i kontrolowania (gdy używasz zbyt wielu podziałów OR zamiast podziałów XOR).

W branży oprogramowania myślę, że to samo dotyczy podobnych problemów związanych z „pokryciem wielu warunków” w analizie pokrycia kodu .

W przypadku firmy najlepszym sposobem jest zmniejszenie przestrzeni problemowej i nie rzucanie więcej zasobów na skomplikowany problem. W moim przykładzie dodaj ograniczenia do przepływu pracy (lub w analizie pokrycia kodu uprość kod), zamiast ciężko pracować nad znalezieniem wszystkich, powiedzmy, N możliwych śladów i wyników, w których N jest niewyobrażalnie dużą liczbą.

Poza tym myślę, że istnieje wiele problemów w analizie sieci / wykresów , których nie można rozwiązać (próba ustalenia topologii sieci poprzez iteracyjne kroczenie wszystkimi ścieżkami itp.).

knb
źródło
0

Klasycznym przykładem jest próba parsowania HTML z wyrażeniami regularnymi . Może to działać z ograniczonymi zestawami HTML, ale ogólne rozwiązanie jest niemożliwe ze względu na fakt, że mają one inną gramatykę Chomsky'ego (jak wyjaśnia link (ish)).

Mówiąc bardziej ogólnie, niektórzy ludzie nie lubią myśleć filozoficznie (jak twój współpracownik) i nie jestem pewien, czy potrafisz wyprowadzić się z umysłu. Jego pierwszy punkt jest z pewnością błędny, ale jego drugi może być po prostu sposobem na powiedzenie, że nie muszę się tym martwić, aby kodować formularze internetowe do odbioru towarów. Mam z tym trochę sympatii, ale czasami znajomość teorii oznacza, że ​​nie angażujesz się w szukanie Świętego Graala w czasie pracy.

Alistair Mackenzie
źródło
-6

Być może odpowiedzią jest, że twój współpracownik ma rację. Być może źle zrozumiałeś Turinga lub jak to tutaj ma zastosowanie?

Wszystkie maszyny są skończone, dlatego nie ma „prawdziwych” maszyn Turinga i programów, które nigdy się nie zatrzymają. Trywialny program, który wykonuje prostą nieskończoną pętlę, może działać 5 minut lub 50 lat, ale na skończonej maszynie się zatrzyma. Zatrzymany zostanie również nietrywialny problem nie zatrzymujący się, taki jak „dokładnie oblicz liczbę pi”, ponieważ ostatecznie obliczenia przekroczą pojemność do przechowywania kolejnych cyfr.

Wynik Turinga nie gwarantuje niczego szczególnie przydatnego na skończonych maszynach, więc twoje zadanie jest ostatecznie bezowocne. Lepiej skoncentruj się na tym, ile czasu i pieniędzy, i pozostaw matematykom nieskończoność.

Może ci się wydawać, że taki program { while true: print "running"; print "halted"; }jest kontrapunktem, ale nim nie jest. Ten program ma skutki uboczne, które mogą powodować zatrzymanie. Ignorując skutki uboczne, można opracować formalny dowód, że ten program się nie zatrzyma. W tym pytaniu zajmujemy się tylko programami, które unikają formalnego dowodu braku zatrzymania, gdy kwestia zatrzymania jest nierozstrzygalna. To nie jest taki program.

Pomoże to odróżnić „silne” Turinga od „słabego” Turinga. Silne maszyny Turinga są w rzeczywistości nieskończone i jeśli się nie zatrzymają, będą działać przez nieskończony czas. Nie możemy ich zbudować.

Słabe maszyny Turinga mają ograniczone limity czasu i przestrzeni i są jedynym rodzajem, jaki możemy zbudować. Interesują nas programy, których zatrzymania w tych granicach nie można udowodnić. Turing mówi nam, że istnieją takie programy, ale nie możemy ich zidentyfikować. Jeśli limity są wystarczająco niskie, możemy je zidentyfikować, pisząc program i uruchamiając go do granic możliwości.

Istotą Turinga jest to, że nie ma skrótów. Jedynym sposobem, aby upewnić się, czy problem jest wykonalny obliczeniowo, jest napisanie programu, uruchomienie go i sprawdzenie. Mając wystarczająco dużo czasu i pieniędzy, możesz napisać wszystkie programy, uruchamiać je na zawsze i z czasem oraz znaleźć te, które przynoszą rezultaty (kantary). Pozostałe nadal będą działać. Czy Twój współpracownik ma wystarczająco dużo czasu i pieniędzy, aby to zrobić?

Poważnie jednak spór dotyczy granic. Turing i NP complete mówią nam, że pewne klasy problemów nie mogą być rozwiązane przez komputery w ramach danego budżetu lub harmonogramu, bez względu na to, jak duży budżet i jak hojny może być ten harmonogram. Przykładów tego rodzaju problemów jest wiele: łamanie kluczy kryptograficznych; optymalizacja tras dostaw do setek adresów; pakowanie pudeł w ciężarówki; znajdowanie błędów w dużych programach!

Poproś więc współpracownika o budżet i harmonogram i złóż obietnicę, że możesz stworzyć problem, którego nie da się rozwiązać w ramach tego budżetu lub harmonogramu. Ta obietnica będzie bardzo łatwa do dotrzymania.

david.pfx
źródło
2
Istota problemu zatrzymania polega na tym, że istnieją klasy problemów, których nie da się obliczyć - nawet przy nieskończonym czasie i pieniądzach. Tego mój współpracownik nie chce zaakceptować.
Jesan Fafon
Wtedy się nie zgadzamy. Zredagowałem swoją odpowiedź, ale zasadniczo wiadomość jest taka sama. Twoje postawione pytanie nie zawiera odpowiedzi (lub takiej, która Ci się nie spodoba), ale leży u podstaw prawdziwego problemu i prawdziwej kwestii. Jeśli chcesz wygrać ten spór, będziesz musiał nieco przesunąć grunt, a ja starałem się w tym pomóc. [Przypomnij mi, żebym nie próbował ponownie odpowiadać na takie pytania - głosy negatywne są niepożądane.]
david.pfx 21.01.14
2
@simon: Ryzykując, że się powtórzę, nie ma programów, których ukończenie zajmuje nieskończoną ilość czasu, ponieważ nie ma kompletnych komputerów Turinga, tylko ich skończone przybliżenia. Nie można udowodnić, że dowolny program zakończy się w określonym czasie za pomocą dowolnej metody, która jest szybsza niż faktyczne uruchomienie programu. W praktyce każde zdanie ze słowem „nieskończony” może nie mieć sensu.
david.pfx
3
while True: print "doing stuff"; print "Finished"; To jest przykład programu, którego ukończenie zajmuje nieskończoną ilość czasu. Istnieje nieskończona ilość innych programów, których ukończenie również zajmuje nieskończoną ilość czasu. Regularnie tworzymy programy, których celowe wykonanie zajmuje nieskończoną ilość czasu. Nazywa się je „procesami długo działającymi”. Większość dynamicznych stron internetowych jest tego przykładem.
Singletoned
2
Chodzi o to, że istnieją zestawy programów komputerowych, które są faktycznie nieskończone, nigdy nie zatrzymają się pod własną parą (w końcu wciskamy przerwę, wyciągamy moc itp.), Jeśli zaprogramowalibyśmy je w maszynie Turinga, to biegnij bez zatrzymywania się. Istota problemu zatrzymania polega na tym, że praktycznie ani teoretycznie nie można ustalić programów nie zatrzymujących się w ogóle algorytmicznie.
Alistair Mackenzie