>Czyli z zegarem rozwiązalibyśmy problem w czasie wykładniczym ... ale co jeśli taki układ byłby bez zegara/synchronizacji?

Jeżeli opis działania urządzenia nie zależy od żadnego sygnału synchronizacji to co tutaj oznacza pojęcie "złożoności" ? Względem czego ją liczymy ? Bo żeby odpowiedzieć na to pytanie musielibyśmy wiedzieć czym jest operacja elementarna dla tego algorytmu.

.

No właśnie, po usunięciu zegara dostajemy hydrodynamikę elektronów - z ładnie uporządkowanego układu cyfrowego dostajemy coś co działa w ciągłym czasie, oraz pewnie pomiędzy dyskretnymi wartościami bramek logicznych ... szczegóły bardzo zależą od technologii układu, nieliniowości tranzystorów ... ale możemy mówić o złożoności, np. jako szybkości stabilizacji takiego układu w zależności od wielkości.

Nie musząc przechodzić przez wykładniczą ilość możliwości, stabilizacja powinna być dość szybka - pewnie w "czasie wielomianowym" i to z niewielką potęgą.

Tylko pytanie czy po takiej stabilizacji, wynik miałby sens?
Obawiam się że zwykle nie - z doświadczenia w przedstawianiu trudnych problemów jako globalna optymalizacja, często dookoła każdego inputu pojawiają się lokalne minima - które "okłamują kilka klauzul/bramek", kształt tych minimów bardzo zależy od nieliniowości.

Tutaj myślę że też będzie wykładnicza ilość takich lokalnych optimów - w których tylko kilka bramek okłamuje: kończy gdzieś między zerem i jedynką.

Jeśli tak, pytanie czy warunek stabilizacji w punkcie stałym pętli jest wystarczająco silnym atraktorem - prawdopodobieństwo wylądowania tam maleje nie wykładniczo, tylko np. wielomianowo?
Jeśli tak, powtarzając rundy szumu, termalizacji i testu, moglibyśmy w wielomianowej ilości rund rozwiązać postawiony problem ... ale prawdopodobnie ten atraktor jednak będzie malał wykładniczo (?)

Może "wzmacniając technologię" można poprawić - np. dokładając redundancję zabezpieczającą przed okłamywaniem przez pojedyncze bramki ... ale obawiam się że to może być błędne koło jak dla kwantowej korekcji błędów: dołożenie redundancji dokłada kolejne bramki które znowu mogą skłamać ... sugerując że może nigdy nie uda się poprawić ponad klasyczne obliczenia (?) :/

>No właśnie, po usunięciu zegara dostajemy hydrodynamikę elektronów - z ładnie uporządkowanego układu cyfrowego dostajemy coś co działa w ciągłym czasie, oraz pewnie pomiędzy dyskretnymi wartościami bramek logicznych ... szczegóły bardzo zależą od technologii układu, nieliniowości tranzystorów ... ale możemy mówić o złożoności, np. jako szybkości stabilizacji takiego układu w zależności od wielkości.

Takiego ciągłego układu fizycznego nie dałoby się teoretycznie symulować obliczeniowo ?
(maszyna Turinga) Bo jeśli układ można symulować obliczeniowo to jeśli chodzi o złożoność formalnie i tak nie może to dać żadnej przewagi. Ewentualnie rozwiązanie sprzętowe mogłoby dać jedynie przewagę praktyczną dla problemów mniejszych od pewnej wielkości, jeśli koszt dyskretnej symulacji jest rzeczywiście duży.

>Nie musząc przechodzić przez wykładniczą ilość możliwości, stabilizacja powinna być dość szybka - pewnie w "czasie wielomianowym" i to z niewielką potęgą.

Rozumiem, że zakładamy, że powyższego układu fizycznego nie da się symulować obliczeniowo i mówimy tutaj o jakimś uogólnieniu pojęcia złożoności i obliczalności ?

Coś jak:

Noncomputability in models of physical phenomena - Pour-El M.B., Richards I.

.

Właśnie takiej możliwości klasycznej symulacji się obawiam: wydaje się że dostajemy typową sytuację z konwersji trudnego problemu na problem globalnej optymalizacji, gdzie np. schodzimy po gradiencie ... do jednego z wykładniczej ilości lokalnych minimów.

Jak w problemie subset-sum: mamy (duże) liczby naturalne k_i, pytanie czy hiperpłaszczyzna prostopadła do wektora k przecina {-1,1}^n ?
Jako problem globalnej optymizacji: na hiperpłaszczyźnie minimalizujemy odległość do najbliższego wierzchołka.
Schodząc po gradiencie, mamy mamy zwykle wykładniczo wiele atraktorów odpowiadających różnym wierzchołkom.
Interesujący nas atraktor: do minimalnej odległości zero, zwykle nie wyróżnia się wystarczająco żeby ułatwić szukanie.

To jest problem występujący też np. w adiabatycznych komputerach kwantowych, dla których jestem zupełnie sceptyczny, w artykułach rozważają np. 4 minima ... podczas gdy dla trudnych problemów jest ich ciut więcej.

Tutaj sytuacja wygląda odrobinę lepiej ze względu na istotne wyróżnienie interesujących nas rozwiązań: stabilnego przepływu, dla gigantycznych ilości elektronów (10^20+).
Pytanie czy to wyróżnienie jest wystarczające żeby jego atraktor przestał wykładniczo zanikać? Prawdopodobnie nie (?)

ps. także sceptyczna praca Scotta Aaronsona odnośnie różnych fizycznych podejść: arxiv.org/pdf/quant-ph/0502072.pdf

>Wydaje się naturalnym sposobem konwersji problemu NP na system fizyczny jest szukanie punktu stałego pętli
Hm.. na pierwszy rzut oka wygląda to na zwykłą pętlę. Czym powyższy koncept różni się od poniższego pseudokodu?
Cytat:

>Czyli z zegarem rozwiązalibyśmy problem w czasie wykładniczym ... ale co jeśli taki układ byłby bez zegara/synchronizacji?
Układy asynchroniczne są znane chyba nawet wcześniej niż synchroniczne; w końcu podstawowe bramki logiczne zawsze są asynchronicznie.. w oparciu o tę zasadę w latach dziewięćdziesiątych były budowane nawet bloki logiczne procesorów (bodajże AMD eksperymentował z takimi konstrukcjami, gdzie FPU w procesorze architektury x86 wykonywane były obliczenia asynchronicznie), całe procesory (bodajże 8080 miał swoją 'asynchroniczną' wersję), a przemysłowo stosowane pamięci RAM pracowały wyłącznie według tej zasady (pamięci FPM, później EDO stosowane w modułach typu SIMM). Późniejsze układy SD-, później DDRAM wprowadziły już zegar. Dlaczego? Z tego samego powodu, dla jakiego układy synchroniczne wygrały wszędzie. Projektowanie systemów asynchronicznych jest dużo bardziej złożone niż opartych o zegar, co powodowało ogromne koszty projektowe. Zagadnienie było mocno drążone w literaturze w latach osiemdziesiątych, kiedy to wydawało się, że właśnie takie rozwiązania to przyszłość informatyki.

Jeżeli chodzi o wydajność, to przyrost prędkości był nieznaczny. Problem podstawowy to czas propagacji sygnału w bloku logicznym w krytycznej ścieżce - w układzie synchronicznym jest on niewiele mniejszy niż okres zegara. Bardzo problematyczne jest natomiast zaprojektowanie układu asynchronicznego realizującego złożoną funkcję.

Podejście jest najzupełniej słuszne ('zaprogramujmy' układ narzucając pewną fizyczną reprezentację zagadnienia, podajmy na wejścia dane w postaci pewnych fizycznych wartości, poczekajmy aż układ się ustabilizuje i to co się ustali na wyjściach jest rozwiązaniem) i było stosowane w układach analogowych, a zapewne będzie stosowane w układach kwantowych, ale niestety w układach cyfrowych działać to nie ma prawa. Podstawowy problem jest taki, że w układzie cyfrowym obliczenia prowadzi się nie na fizycznych wartościach, a ich abstrakcyjnych reprezentacjach, co ma swoje zalety w stosunku do obliczeń prowadzonych na układach fizycznych, ale i wady - jedną z nich jest brak możliwości prowadzenia takich 'analogowych' obliczeń. Niemniej jednak maszyny wykorzystujące tę zasadę - analogowe komputery - były z najlepszym pożytkiem budowane i wykorzystywane w latach sześćdziesiątych, siedemdziesiątych i osiemdziesiątych ubiegłego wieku. Program Apollo był zresztą wielką sensacją między innymi dlatego, że pokładowy komputer wspomagający obliczenia trajektorii był maszyną cyfrową, a nie jak typowe wtedy maszyny tej wielkości - analogową.

Rzeczywiście z zegarem w kolejnych krokach testowalibyśmy kolejne wejścia aż do ustabilizowania w punkcie stałym rozwiązującym nasz problem.
Pytanie co się dzieje bez zegara?

Podczas gdy całkowicie się zgadzam że ogólnie asynchroniczne układy logiczne są niezwykle trudne do zaprojektowania, szczególnie ze względu na synchronizację, tutaj możemy przyjąć że układ ma niezwykle prostą budowę, np. w postaci 3-SAT, czyli tester sprawdza czy wszystkie alternatywy ustalonych trójek są spełnione, np.:

(x OR not y OR z) AND (y OR z OR not u) AND ...

Czyli (błędnie) zakładając wielowejściowe AND/OR, tester ma tylko powiedzmy 3 warstwy: liczenie negacji, potem alternatyw w ustalonych trójkach, potem koniunkcji wszystkiego.

Czy taki prosty asynchroniczny układ o ustalonej strukturze, bez problemu synchronizacji, ma szansę szybko zbiegać do punktu stałego pętli - rozwiązującego postawiony problem?

>Pytanie co się dzieje bez zegara?
Mitologizujesz bardzo ów prosty wybieg, jakim jest zegar, który praktycznie stanowi jedynie wygodne obejście problemu synchronizacji ścieżek poszczególnych bloków funkcjonalnych układu. Jeżeli układ asynchroniczny jest dobrze zaprojektowany, to odpowiedź jest prosta: dzieje się to samo, co i w układzie z zegarem.

>Czy taki prosty asynchroniczny układ o ustalonej strukturze, bez problemu synchronizacji, ma szansę szybko zbiegać do punktu stałego pętli - rozwiązującego postawiony problem?
Nie ma takiej możliwości. Układ fizyczny prowadzi obliczenia w zupełnie inny sposób, niż układ cyfrowy (nieważne czy synchroniczny, czy nie) pracujący na abstrakcjach, choć wciąż oba są równoważne.

Zresztą niezbyt klarownie wyjaśniłeś o co chodzi z testerem, podając jako przykład prostą funkcję logiczną, podczas gdy do ilustracji problemu potrzebna byłaby funkcja 3x3 (3 wejścia, 3 wyjścia). Sama próba przygotowania takiej ilustracji pokazałaby już problemy przy zbudowaniu sensownej synchronizacji takiego układu.

Czyli rzeczywista częstotliwość dobrze zaprojektowanego układu asynchronicznego (bez zegara) zależy od charakterystyk tranzystorów, opóźnień na ścieżkach, etc. ... wydaje się to niewyobrażalne że da się to uporządkować, ale rzeczywiście widzę że potrafią nawet tak budować procesory:
en.wikipedia.org/wiki/Asynchronous_circuit

To jeszcze może rozpiszę mój przykład, ale rzeczywiście przy dobrej synchronizacji powinien się zachować jak z zegarem - stabilizując po wykładniczej ilości cykli ... choć można się zapytać co jeśli wybijemy taki układ z synchronicznego działania poprzez np. szum - tak żeby szukał stałego punktu pętli działając poza binarnymi wartościami i w sposób niesynchroniczny?

Więc przyjmijmy że w zadanym 3-SAT mamy n zmiennych (x,y,z,...) oraz m klauzul: alternatyw trójek, np.
"x OR not y OR z" to jedna z takich m trójek, w których część zmiennych może być zanegowana, zmienne oczywiście mogą się powtarzać między trójkami.

Czyli taki "pętlowy układ" to jest:
- znalezienie negacji wszystkich zmiennych (1 operacja równolegle),
- obliczenie OR dla wszystkich ustalonych trójek (1-2 operacje równolegle) - tutaj jest zapisana konkretna instancja problemu,
- obliczenie AND po wszystkich trójkach (w praktyce drzewko o log2(n) warstwach) - ten wynik mówi 1 iff wejście jest satysfakcjonujące,
- wykonanie "if satisfying return input, else return input+1", czyli po prostu dodanie "NOT wynik koniunkcji z poprzedniej warstwy" do wektora zmiennych (drzewko o ~log2(m) warstwach), to "+1" jest cyklicznie czyli po prostu pomijamy najstarszy bit,
- wynikły ciąg bitów dajemy na wejście, zamykając pętlę.

Startując od zupełnego szumu, jak powinien zachować się taki układ?
Czy działając niesynchronicznie, poza dyskretnymi wartościami, ma szansę szybciej się ustabilizować na punkcie stałym pętli?

>Czyli rzeczywista częstotliwość dobrze zaprojektowanego układu asynchronicznego (bez zegara) zależy od charakterystyk tranzystorów, opóźnień na ścieżkach, etc.
Dokładnie.

>To jeszcze może rozpiszę mój przykład, ale rzeczywiście przy dobrej synchronizacji powinien się zachować jak z zegarem - stabilizując po wykładniczej ilości cykli ... choć można się zapytać co jeśli wybijemy taki układ z synchronicznego działania poprzez np. szum - tak żeby szukał stałego punktu pętli działając poza binarnymi wartościami i w sposób niesynchroniczny?
Ech, cóż za magia tkwi w owym usunięciu zegara.. chyba taki sam urok opadł na informatykę pod koniec lat osiemdziesiątych, gdy wydawało się że takie układy to przyszłość.
Chciałbyś, żeby układ cyfrowy, pracujący na abstrakcjach zaczął pracować jak układ analogowy pracujący na fizycznych reprezentacjach wyłącznie dzięki zmianie synchronizacji z jawnej, opartej o osobny sygnał na niejawną synchronizację układu asynchronicznego? Na dodatek zakłóconą szumem?.. nie, to tak działać nie będzie. Wybity z synchronizacji' układ 'pójdzie w krzaki' i przestanie w ogóle wykonywać jakiekolwiek sensowne przetwarzanie.

>Czy działając niesynchronicznie, poza dyskretnymi wartościami, ma szansę szybciej się ustabilizować na punkcie stałym pętli?
Wytłumacz proszę, co rozumiesz pod pojęciem 'układu cyfrowego działającego niesynchronicznie poza dyskretnymi wartościami'. Bo dla mnie to jakieś bzdury. Jak układ cyfrowy może działać poza dyskretnymi wartościami? I jak dyskretyzacja sygnału ma się do synchronizacji, ze brak drugiej prowadzi do wyjścia poza pierwsze? Układ miałby obliczając wyjść z siebie i stanąć obok? Wtedy rzeczywiście mogłoby być szybciej, bo działałyby dwa układy

>Startując od zupełnego szumu, jak powinien zachować się taki układ?
A jak zachowałby się taki układ w wariancie synchronicznym, gdyby startował od szumu?

>Wytłumacz proszę, co rozumiesz pod pojęciem 'układu cyfrowego działającego niesynchronicznie poza dyskretnymi wartościami'. Bo dla mnie to jakieś bzdury. Jak układ cyfrowy może działać poza dyskretnymi wartościami? I jak dyskretyzacja sygnału ma się do synchronizacji, ze brak drugiej prowadzi do wyjścia poza pierwsze? Układ miałby obliczając wyjść z siebie i stanąć obok? Wtedy rzeczywiście mogłoby być szybciej, bo działałyby dwa układy
To że układ cyfrowy pracuje na dyskretnych wartościach zawdzięczamy m.in. temu że tranzystor ma "wąską funkcję progu" (charakterystykę) pomiędzy dwoma dyskretnymi stanami.
Jednak fizycznie tam jest pewna nieliniowa ciągła funkcja (źródło animacji poniżej), teoretycznie taki układ może pracować między dyskretnymi wartościami, szczególnie jeśli funkcja progu jest względnie szeroka.


Zaczynając od zupełnego szumu dla takiego układu, może mu się udać zsynchronizować tak że zacznie działać jakby był z zegarem - znajdując rozwiązanie w czasie wykładniczym
... ale czy może mu się nie udać zsynchronizować? - kiedy to będzie fluktuował w sposób asynchroniczny, też operując między dyskretnymi wartościami - na zboczu funkcji progu.

Wydaje mi że taki układ nie musi zawszę się sam zsynchronizować (?) - co jeśli mu się nie uda?
1) Czy będzie już tylko "szumiał/fluktuował" w nieskończoność?
2) Czy może, skoro istnieje punkt stały pętli - stabilny przepływ rozwiązujący postawiony problem, w końcu ten szum ustabilizuje się na takim stabilnym przepływie - intuicyjnie "wygładzając turbulencje tej hydrodynamiki elektronów" ?
3) A może ustabilizuje się na sytuacji która nie rozwiązuje naszego problem - np. zostawiając kilka "okłamujących bramek": pomiędzy dyskretnymi wartościami?

>To że układ cyfrowy pracuje na dyskretnych wartościach zawdzięczamy m.in. temu że tranzystor ma "wąską funkcję progu" (charakterystykę) pomiędzy dwoma dyskretnymi stanami.
Hm.. tranzystor jest całkowicie analogowym obwodem i nie posiada 'dyskretnych stanów'. Zwłaszcza takich, które można synchronizować pomiędzy różnymi tranzystorami. Dopiero układy takich tranzystorów skonfigurowane w bramki mają swoje umówione fizycznymi wartościami stany dyskretne, tyle że zaszumienie sygnału przenoszonego pomiędzy bramkami do niczego dobrego nie doprowadzi.

Wciąż próbujesz wcisnąć zasadę działania układu analogowego w cyfrowy obwód. To nie zadziała.. albo ja czegoś jeszcze nie wiem. W każdym razie powodzenia.

>Hm.. tranzystor jest całkowicie analogowym obwodem i nie posiada 'dyskretnych stanów'. Zwłaszcza takich, które można synchronizować pomiędzy różnymi tranzystorami. Dopiero układy takich tranzystorów skonfigurowane w bramki mają swoje umówione fizycznymi wartościami stany dyskretne, tyle że zaszumienie sygnału przenoszonego pomiędzy bramkami do niczego dobrego nie doprowadzi.
Owszem, ale bramki budujące dyskutowany układ są zbudowane z tranzystorów - tam fizycznie jest też jakieś zachowanie pomiędzy dyskretnymi/cyfrowymi stanami ... szczególnie jeśli stan początkowy jest np. ciągłym szumem a nie dyskretnym sygnałem.
Np. łącząc bramkę NOT w pętlę, czyli tworząc tzw. ring ooscillator, nie dostajemy idealnych prostokątnych progów, tylko np.:


>Wciąż próbujesz wcisnąć zasadę działania układu analogowego w cyfrowy obwód. To nie zadziała.. albo ja czegoś jeszcze nie wiem. W każdym razie powodzenia.
Czyli uważasz że taki układ - pętla o stabilnym przepływie rozwiązującym nasz problem - po wystartowaniu od szumu (nie-dyskretnego), zawsze się sama zsynchronizuje?
Jeśli nie to czy będzie fluktuować w nieskończoność, czy może sama powinna się ustabilizować mimo braku synchronizacji?
Jeśli sama się powinna ustabilizować to jak szybko i czy na rozwiązaniu naszego problemu?

Przyjacielu, tak post scriptem muszę przyznać, iż obawiam się, że masz bardzo blade pojęcie o zasadzie działania układów cyfrowych, co wykazałeś w pierwszej i fragmentarycznie drugiej części powyższego wpisu. Ze snucia czarujących, choć bezsensownych opisów w rodzaju '[układ cyfrowy] szuka stałego punktu pętli działając poza binarnymi wartościami i w sposób niesynchroniczny' widać również, żeś beznadziejnie zakochany w swoim koncepcie, bo jakżeby inaczej można zinterpretować Twą wyprowadzoną ze stwierdzenia 'nie działa' sugestię, że mógłbym uważać iż nie dość owo dziwadło działać będzie, to jeszcze coś z czymś synchronizowało i na dodatek jeszcze coś rozwiązywało? Toć to wyraźny objaw odurzenia przedmiotem uwielbienia swego.. na to niestety nie znam wyjaśnień które pomóc byłyby zdatne. Może spróbuj leczenia jakąś porządną, akademicką literaturą z dziedziny podstaw elektroniki i układów elektronicznych? A tymczasem miłego dnia życzę..

Odnośnie "bycia zakochanym w tym koncepcie", we wszystkich miejscach wyraźnie piszę że jestem sceptyczny że to może działać i to w czasie istotnie krótszym niż wykładniczy ... jednak jest to jeden z bardzo nielicznych sposobów na przekonwertowanie trudnego problemu obliczeniowego na czysto fizyczny - nie będący "klasycznym komputerem", tylko np. wykorzystujący zdolność fizyki do ciągłego poszukiwania optimum.

Dlatego chciałbym dobrze zrozumieć trudności związane z tym podejściem - co jest daleko nietrywialne oraz przenosi się na trudności innych podejść (szczególnie adiabatycznych komputerów kwantowych).
Zamiast nic nie wnoszącej generalnej krytyki (no to jak w końcu uważasz że powinien się zachowywać?), może mógłbyś po prostu odpowiedzieć na konkretne pytania które zadałem:
1) czy taki układ bez zegara będzie zawsze sam się synchronizował? (ostatecznie zachowując jak układ z zegarem)
2) jeśli nie to czy będzie "szumiał" w nieskończoność, czy może jednak powinien zbiec do stabilnego przepływu - wyobrażając sobie że tam są amperomierze, wskazywałyby one niekończące się fluktuacje, czy ostatecznie ustabilizowałyby się na stałych wartościach?
3) Jeśli będą się stabilizowały, to jak szybko i czy taki finalny stan będzie odpowiadał rozwiązaniu naszego problemu?

Osobiście myślę że wszystkie trzy opcje mogą występować w zależności od szczegółów/parametrów, ale w 3) przypadku zwykle nie będzie rozwiązywał naszego problemu, "kłamiąc" na kilku bramkach: ustawiając je pomiędzy dyskretnymi wartościami.

Przyjacielu, odpowiedziałem przynajmniej trzykrotnie, z których to odpowiedzi co do przynajmniej jednej zaczynałeś sprawiać wrażenie, że pojmujesz. Dlaczegoś porzucił tę drogę?

Jako niespecjalista niczego nie jestem w stanie wyrozumieć ze slajdów,
oprócz paru znajomych wzorków. Gdzie o tym można poczytać od podstaw?

Aha, co rozumiesz przez "fizykę rozwiązującą problem"? Np. że idealny
kodensator rozładowujący się przez opornik "rozwiązuje" równanie liniowe
pierwszego rzędu i dostajesz funkcję wykładniczą?...

Najważniejszy znany przykład to jest (kwantowy) algorytm Shora - rozwiązujący w czasie wielomianowym problem faktoryzacji, dla którego nie znany (jeszcze?) jest wielomianowy klasyczny algorytm: en.wikipedia.org/wiki/Shor's_algorithm

Bardzo głośno jest o adiabatycznych jak D-wave ( en.wikiped(*)/Adiabatic_quantum_computation ) - zamieniają one trudny problem na globalną optymalizację ... tyle że w ten sposób dla trudnych problemów pojawia się wykładnicza ilość lokalnych minimów, podczas gdy interesuje nas tylko globalne ...
Myślę że podobny problem występuję w podejściu z tego wątku (?)

ps. jeszcze są komputery DNA: en.wikipedia.org/wiki/DNA_computing

Dziękuję, może w ramach odtrutki od "klasycznych" spraw zajrzę.

Stara acz dalej dająca do myślenia przeglądówka Aaronsona: arxiv.org/pdf/quant-ph/0502072.pdf

Nie, z tego nic nie rozumiem - to dla "wprowadzonych"