Czy można rozwiązać problem złożoności O (n!) W rozsądnym czasie, biorąc pod uwagę nieskończoną liczbę jednostek przetwarzania i nieskończoną przestrzeń?Ograniczenia paralelizmu (pytanie o rozmowę kwalifikacyjną)
Typowym przykładem problemu O (n!) Jest przeszukanie brute-force: próba wszystkich permutacji (uporządkowane kombinacje).
Na pewno jest. Zastanów się nad problemem podróżnego sprzedawcy w jego ścisłej formie NP: biorąc pod uwagę tę listę kosztów podróży z każdego punktu do drugiego punktu, czy możesz ułożyć trasę o cenie mniejszej niż K? Z nowym, nieskończonym procesorem firmy Intel, wystarczy przypisać jeden rdzeń do każdej możliwej permutacji i zsumować koszty (jest to szybkie) i sprawdzić, czy którekolwiek z podstawowych flag zakończyło się sukcesem.
Ogólnie rzecz biorąc, problemem w NP jest problem decyzyjny, taki, że potencjalne rozwiązanie można zweryfikować w czasie wielomianowym (tj. Efektywnie), a zatem (ponieważ potencjalne rozwiązania są możliwe do przeliczenia), każdy taki problem można skutecznie rozwiązać za pomocą wystarczająco dużo procesorów.
Oczywiście, można wyliczyć wszystkie możliwe rozwiązania, ale jak zapewnić każdemu procesorowi wymagane dane? Musisz dystrybuować dane i oznacza to, że musisz porównać każdą permutację ze sobą. – psihodelia
Nie, nie musisz porównywać wszystkiego ze wszystkim. Załóżmy, że potrzebujesz rozwiązania o najniższych kosztach dla TSP. Oblicz wszystkie koszty równolegle. Następnie procesory z parzystymi numerami porównują swoje wartości z odpowiednimi wartościami nieparzystymi i utrzymują bardziej ekonomiczny wynik. Dokonaj takiego porównania i możesz uzyskać odpowiedź w czasie potrzebnym na log n! porównania. O (n^n)> = O (n!) I log (n^n) to n log n, więc przetwarzanie końcowe byłoby w najgorszym O (n log n), które jest wielomianem. Byłoby możliwe, aby przynajmniej tak dobrze było przy konfiguracji. –
Spójrzmy na TSP, który: Biorąc pod uwagę kompletny wykres ważony, znajdź cykl hamiltonowski o najmniejszej wadze. Musisz mieć deterministyczną procedurę, aby stworzyć unikalny cykl Hamiltona na każdym procesorze. Musisz przypisać każdy możliwy cykl do każdego procesora. Nawet jeśli obliczenie długości cyklu można wykonać w całkowicie niezależnym wątku przetwarzania, istnieje n! cykle. Pytanie brzmi: czy wszystkie cykle mogą być przypisane do procesorów niezależnie? Nie dlaczego? Ze względu na deterministyczny charakter rachunku. – psihodelia
Pomijając koszty konfiguracji (cokolwiek to może być np. Przypisanie zakresu wartości do jednostki przetwarzania), a następnie tak. W takim przypadku dowolna wartość mniejsza niż nieskończoność może być rozwiązana w jednej równoczesnej iteracji przez równą liczbę jednostek przetwarzania.
Konfiguracja jest jednak czymś ważnym do zignorowania.
Dlaczego każda wartość jest mniejsza niż nieskończoność? Biorąc pod uwagę nieskończoną liczbę procesorów, czy nie powinni oni być w stanie obsłużyć równej liczby (nieskończonych) procesów? Nieskończoność rani mój mózg czasem – Bob
@ Bob: Ponieważ każda wartość jest mniejsza niż nieskończoność;) –
Nie, ponieważ zajmuje nieskończenie dużo czasu, aby rozprowadzić pracę do nieskończonych maszyn - również zajmuje naprawdę dużo czasu, aby otworzyć skrzynki i zainstalować je. –
Wygląda na to, że naprawdę pytasz, czy problem złożoności O (n!) Można zredukować do O (n^a) na niedeterministycznej maszynie; innymi słowy, czy Not-P = NP. Odpowiedź na to pytanie brzmi: nie, są pewne problemy nie-P, które nie są NP. Na przykład ograniczony problem z zatrzymaniem (który pyta, czy program zatrzymuje się co najwyżej n! Kroków).
Wziąłem odpowiedź, jeśli istnieją problemy, które można łatwo rozwiązać. Odpowiadasz na wszystkie problemy, które są równie uzasadnione i na które większość osób nie odpowiada. –
To prawda. Uważam, że nasze odpowiedzi są komplementarne: są pewne problemy, które redukują, a inne nie. Oba fakty są ważne. – tloflin
Problem polegał na dystrybucji pracy i zbieraniu wyników.
Jeśli wszystkie procesory mogą odczytywać tę samą pamięć jednocześnie, a każdy z nich ma unikatowy identyfikator CPU-ID, to identyfikator może zostać użyty do wybrania permutacji, a problem z dystrybucją jest rozwiązalne w stałym czasie.
Gromadzenie wyników byłoby jednak trudne. Każdy procesor może porównać z jego (numerycznym) sąsiadem, a następnie wynik w porównaniu do wyniku dwóch najbliższych sąsiadów itd. Będzie to proces O (log (n!)). Nie wiem na pewno, ale podejrzewam, że O (log (n!)) Jest hiperpolynomialny, więc nie sądzę, że to jest rozwiązanie.
O (log (n!))) = O (n log n). To na pewno wielomian. – Daniel
Jeśli problem polega na sprawdzeniu permutacji/odpowiedzi na problem złożoności O (n!), To oczywiście można to zrobić wydajnie z nieskończoną liczbą procesorów.
Powodem jest to, że można łatwo dystrybuować części atomowe problemu (część atomowa problemu może być, na przykład, jedną z permutacji do sprawdzenia) z logarytmiczną wydajnością.
Jako prosty przykład można ustawić procesory jako "drzewo binarne", że tak powiem. Możesz być w katalogu głównym i pozwolić procesorom dostarczyć permutacje problemu (lub cokolwiek najmniejszego elementu problemu) do procesorów liści, aby rozwiązać problem, a skończysz na rozwiązaniu problemu w log (n!) czas.
Pamiętaj, że dostarczenie permutacji procesorom zajmuje dużo czasu. Każda część samego problemu zostanie natychmiast rozwiązana.
Edytuj: Naprawiono mój post zgodnie z komentarzami poniżej.
Ponieważ liczba procesorów używanych w problemie jest n! zamiast n, konfiguracja "drzewa binarnego" odbywa się w kolejności log (n!). –
Masz rację. Mój błąd! – Cam
log n! jest wystarczająco dobre. Jest to wielomian (choć zdecydowanie nie jest podliniowy). –
Każdy problem może zostać rozwiązany przez jeden procesor, ale kto dostarczy te zadania do wszystkich nieskończonych procesorów? Zasadniczo to zadanie jest scentralizowane, więc jeśli mamy nieskończone zadania do dostarczania do wszystkich nieskończonych procesorów, możemy poświęcić na to nieskończony czas.
W rzeczywistości dla większości rzeczywistych problemów dystrybucja zleceń jest procesem równoległym, więc dla O (n!) Problemów dystrybucja to O (n log n). –
Nie, N! jest nawet wyższa niż NP. Myślenie o nieskończonej równoległości mogłoby rozwiązać problem NP w czasie wielomianowym, który jest zwykle uważany za "rozsądną" złożoność czasu, N! problem jest wciąż wyższy niż wielomian w takiej konfiguracji.
* N! jest nawet wyższa niż NP * - [potrzebne źródło]. I czy jest to nawet istotne? Dopóki wynik jest możliwy do sprawdzenia w czasie wielomianowym, to jest w NP. – kennytm
Rozsądnie jest powiedzieć, że O (n!) Jest wyższe niż O (2^n), ponieważ porównuje się to z podobnym. Jednak problem NP jest definiowany jako problem, który można rozwiązać w czasie wielomianowym na niedeterministycznej maszynie Turinga, lub równoważnie, z wynikami, które można zweryfikować w czasie wielomianowym. Nie mówi nic o złożoności czasu na znalezienie rozwiązania. Dlatego po prostu nie rozumiem, co masz na myśli, mówiąc o swoim oświadczeniu. –
@KennyTM: Przepraszam za nadużycie notacji NP.W jakiś sposób spostrzegłem, że problemy NP mają formę k^N, być może z powodu wszechwładzy jej akademickiej definicji. Masz rację, nie powinienem był używać NP w mojej pierwotnej odpowiedzi i nie ma żadnego cytatu na moje oświadczenie. Jednak jeśli problem jest możliwy do zweryfikowania w czasie wielomianowym, odradza się od problemu do problemu. Moim początkowym zamiarem było stwierdzenie, że są pewne problemy z N! złożoności nie można zweryfikować w czasie wielomianowym nawet przy nieograniczonej równoległości. – Codism
Wspomniałeś o wyszukiwaniu jako "typowym" problemie, ale czy rzeczywiście zapytano Cię o problem z wyszukiwaniem? Jeśli tak, to tak, wyszukiwanie jest zazwyczaj możliwe do zrównoleglenia, ale o ile mogę powiedzieć, że O (n!) W zasadzie nie oznacza, że dostępny jest stopień współbieżności, prawda? Możesz mieć całkowicie szeregowy problem O (n!), Co oznacza, że nieskończone komputery nie pomogą. Miałem kiedyś nietypowy problem O (n^4), który w rzeczywistości był całkowicie seryjny.
Tak więc, dostępna współbieżność jest pierwszą rzeczą, a IMHO powinieneś zdobyć punkty za podniesienie prawa Amdahla w wywiadzie. Kolejną potencjalną pułapką jest komunikacja między procesorami i ogólnie natura algorytmu. Rozważmy na przykład tę listę klas aplikacji: http://view.eecs.berkeley.edu/wiki/Dwarf_Mine. FWIW kod O (n^4), o którym wcześniej wspominałem, zalicza się do kategorii FSM.
Kolejna nieco podobna anegdota: Słyszałem, że inżynier z superkomputerowego producenta twierdzi, że jeśli 10% czasu pracy procesora zostało wydane w bibliotekach MPI, uważają, że proces równoległy jest niezłym sukcesem (choć mogło to być po prostu ograniczone do kodów w domenie chemii obliczeniowej).
To jest jak pytanie, czy nieskończona liczba małp piszących na komputerze odpornym na zniszczenie małp z edytorem tekstu może wymyślić wszystkie dzieła Szekspira; biorąc pod uwagę nieskończoną ilość czasu. Reality powiedziałby, że nie, ponieważ warunki nie są fizycznie możliwe. Idealiści powiedzą tak; teoretycznie może się zdarzyć. Ponieważ inżynieria oprogramowania (inżynieria oprogramowania, a nie informatyka) koncentruje się na rzeczywistym systemie, który możemy zobaczyć i dotknąć, wtedy odpowiedź brzmi "nie". Jeśli w to wątpisz, to zbuduj i udowodnij, że się mylę! MOIM ZDANIEM.
Czasami poprawna odpowiedź brzmi: "Ile razy przychodzi to z bazą kodu?" ale w tym przypadku istnieje prawdziwa odpowiedź.
Prawidłowa odpowiedź brzmi "nie", ponieważ nie wszystkie problemy można rozwiązać, stosując idealne przetwarzanie równoległe. Na przykład problem przypominający komiwojażera musi uwzględniać jedną ścieżkę, aby można było rozważyć drugi etap podróży.
Zakładając w pełni połączoną matrycę miast, jeśli chcesz wyświetlić wszystkie możliwe nie-cykliczne trasy dla naszego znużonego sprzedawcy, utknąłeś z problemem O (n!), Który można rozłożyć na O (n) * O ((n-1)!) Problem. Problem polega na tym, że musisz zatwierdzić jedną ścieżkę (po stronie O (n) równania), zanim będziesz mógł rozważyć pozostałe ścieżki (po stronie O ((n-1)!) Równania).
Ponieważ niektóre obliczenia muszą być wykonywane przed innymi obliczeniami, nie ma możliwości równomiernego rozproszenia wyników w jednym przebiegu rozproszonym/zbierania. Oznacza to, że rozwiązanie będzie czekało na wyniki obliczeń, które muszą nastąpić przed rozpoczęciem "następnego" kroku. Jest to kluczowe, ponieważ potrzeba wcześniejszych częściowych rozwiązań zapewnia "wąskie gardło" w zdolności do wykonywania obliczeń.
Ponieważ udowodniliśmy, że możemy sprawić, że wiele z tych nieskończenie szybkich, nieskończenie licznych procesorów czeka (nawet jeśli czekają na siebie), wiemy, że środowisko wykonawcze nie może być O (1), a my potrzebujemy tylko wybrać bardzo duży N, aby zagwarantować "niedopuszczalny" czas pracy.
Nie. Rozdziel permutacje między procesorami, co jest operacją wielomianową. Każdy procesor oblicza swój koszt permutacji, który jest również wielomianem, a właściwie O (n). Potem następuje porównanie hierarchiczne, które jest również wielomianem. –
Nie można rozprowadzać wszystkich permutacji między procesorami bez eksploracji przestrzeni permutacji. Gdybyś podjął strzelbę, mógłbyś przegapić permutacje (i na pewno byłoby dużo nakładania się), a "faza rekombinacji" zapłaciłaby cenę konieczności sortowania przez tony duplikatów, które nadal zajmowałyby ją powyżej O (1) sprawiając, że jest on nadal "nierozsądny", dzięki czemu zestaw rozwiązań jest wystarczająco duży. –
Tak, jeśli n!
mob
Chcę wiedzieć, gdzie rozmawiałeś. To niesamowite, że mają komputer z nieskończonymi procesorami i pamięcią! –
@Jeff: Tee hee. – Pierreten