Algorytmy DNA i kompletność NP

Jaki jest związek między algorytmami DNA a klasami złożoności określonymi za pomocą maszyn Turinga? Czym są pomiary złożoności, takie jak czas i przestrzeń w algorytmach DNA? Czy można je wykorzystać do rozwiązania problemów związanych z NP-zupełnymi, takich jak TSP, których maszyny von Neumann nie są w stanie rozwiązać w praktyce?

Odpowiedź Soundbite: obliczenia DNA nie zapewniają magicznej różdżki do rozwiązania problemów z NP-zupełnym, chociaż niektórzy szanowani badacze w latach 90. myśleli, że tak się stanie.

Inauguracyjny eksperyment z wykorzystaniem DNA przeprowadzono w laboratorium pod kierunkiem znanego teoretyka liczb Len Adlemana. Adleman rozwiązał mały problem wędrownego sprzedawcy - dobrze znany problem NP-zupełny, a on i inni myśleli przez chwilę, że metoda może się zwiększyć. Adleman opisuje swoje podejście w tym krótkim filmie , który wydaje mi się fascynujący. Problem, który napotkali, polegał na tym, że aby rozwiązać problem niewielkiej wielkości TSP, potrzebowaliby więcej DNA niż wielkości Ziemi. Wymyślili sposób na zaoszczędzenie czasu poprzez zwiększenie ilości pracy wykonanej równolegle, ale to nie znaczyło, że problem TSP wymagał mniej niż wykładnicze zasoby do rozwiązania. Dopiero przesunęli koszt wykładniczy z ilości czasu na ilość materiału fizycznego.

(Istnieje dodatkowe pytanie: jeśli potrzebujesz wykładniczej ilości maszyn do rozwiązania problemu, czy automatycznie potrzebujesz wykładniczej ilości czasu lub przynajmniej wstępnego przetwarzania, aby zbudować maszynę w pierwszej kolejności? Zostawiam ten problem z jednej strony.)

Ten ogólny problem - skrócenie czasu obliczeń kosztem innych zasobów - pojawił się wiele razy w biologicznie inspirowanych modelach obliczeniowych. Strona Wikipedii na temat obliczeń błonowych (abstrakcja komórki biologicznej) mówi, że pewien rodzaj systemu błonowego jest w stanie rozwiązać problemy NP-zupełne w czasie wielomianowym. Działa to, ponieważ system ten pozwala na tworzenie wykładniczo wielu podobiektów w całej błonie w czasie wielomianowym. Cóż ... w jaki sposób wykładnicza ilość surowca dociera ze świata zewnętrznego przez membranę o stałym polu powierzchni? Odpowiedź: nie jest brane pod uwagę. Nie płacą za zasób, który w innym przypadku wymagałby obliczeń.

Wreszcie, aby odpowiedzieć na Anthony Labarre, który odesłał do artykułu pokazującego AHNEP, może rozwiązać problemy NP-zupełne w czasie wielomianowym. Istnieje nawet artykuł pokazujący, że AHNEP mogą rozwiązać 3SAT liniowoczas. AHNEP = Akceptacja hybrydowej sieci procesorów ewolucyjnych. Procesor ewolucyjny to model inspirowany DNA, którego rdzeń ma ciąg, który na każdym etapie można zmienić przez podstawienie, usunięcie lub (co ważne) wstawienie. Ponadto w każdym węźle dostępna jest dowolnie duża liczba ciągów, a na każdym etapie komunikacji wszystkie węzły wysyłają wszystkie swoje prawidłowe ciągi do wszystkich dołączonych węzłów. Zatem bez kosztów czasowych możliwe jest przesyłanie wykładniczej ilości informacji, a dzięki regule wstawiania poszczególne ciągi znaków mogą stać się jeszcze większe w trakcie obliczeń, więc jest to podwójne zawroty głowy.

Jeśli interesują Cię najnowsze prace w dziedzinie biokomputacji, badacze skupiający się na obliczeniach praktycznych w świecie rzeczywistym, mogę zaoferować recenzję książki, którą niedawno napisałem dla SIGACT News, która krótko omawia wiele obszarów.

To bardzo zależy od twojego modelu.

W rzeczywistości obliczenia DNA są zgodne z (nierelatywistycznymi) prawami fizycznymi, a zatem mogą być symulowane na komputerze kwantowym. Zatem najlepsze, na co możesz liczyć, to to, że rozwiąże ono problemy kompletne w BQP. Jednak w rzeczywistości jest to bardzo mało prawdopodobne (DNA jest dość duże, więc spójność nie jest tak naprawdę problemem), a więc dzięki symulacji prawie na pewno P. Należy jednak zauważyć, że jest to wydajność pod względem liczby użytych atomów, a szczerze mówiąc, atomy są na tyle tanie, że liczba ta jest astronomiczna, co czyni praktyczną symulację probówki pełnej DNA daleko poza sferą tego, co jest obecnie możliwe.

W rezultacie wiele osób decyduje się na pracę z modelami, które aproksymują to, co dzieje się całkiem dobrze w praktyce, ale psują się, gdy są popychane do skrajności. Jednym z przykładów jest abstrakcyjny model kafelkowy, który, jak się okazuje, jest kompletny w NEXP (patrz artykuł Gottesmana i Irani z FOCS w zeszłym roku).

To jest częściowa odpowiedź

Z artykułu w Wikipedii, o którym wspomniałeś, algorytmy molekularnego obliczania DNA, które rozwiązują problemy z NP-zupełnym, nie dowodzą, że problemy z NP-zupełnym można rozwiązać w czasie wielomianowym na maszynach sekwencyjnych (zakładając, że w praktyce oznacza to czas wielomianowy). Obliczenia DNA można uznać za obliczenia równoległe. Wreszcie, z punktu widzenia teorii obliczalności, obliczenia DNA nie są bardziej wydajne niż maszyny Turinga.

Ten artykuł może być dla ciebie interesujący - nawiasem mówiąc, byłbym wdzięczny, gdyby ktoś mógł wyjaśnić szokujące stwierdzenie, które stanowi jego tytuł.