Pytania otagowane jako ppad

1
Odrzucenie dowodu: amatorskie recenzje ambitnych artykułów KR-u
Myślę, że przeczytałem zbyt wiele ambitnych artykułów KR-u . Problem polega na tym, że dokumenty te nie są recenzowane, ale często brzmią interesująco i przechodzą podstawowe kontrole wiarygodności. A może nie, a ja muszę tylko poprawić swoje kontrole wiarygodności. Oto ostatnia próbka takich dokumentów: Drzewa wyjątkowości: możliwe podejście wielomianowe do …
1
Czy
Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być ważne, więc zastanawiam się, co się dzieje …
2
Czy PPAD naprawdę wychwytuje pojęcie znalezienia innego niezrównoważonego wierzchołka?
Klasa złożoności PPAD została wynaleziona przez Christosa Papadimitriou w jego przełomowym artykule z 1994 roku . Klasa ma na celu uchwycenie złożoności problemów wyszukiwania, w których istnienie rozwiązania jest gwarantowane przez „Argument parzystości w grafach ukierunkowanych”: jeśli w grafie ukierunkowanym występuje niewyważony wierzchołek, musi istnieć inny. Ale zazwyczaj klasa jest …
1
Dlaczego te dwie definicje PPAD są równoważne?
Klasa złożoności PPAD jest zwykle definiowana przez stwierdzenie, że Koniec linii jest kompletny z PPAD. Koniec linii to problem z wyszukiwaniem. Dane wejściowe składają się z ukierunkowanego wykresu, w którym każdy węzeł ma co najwyżej stopień i stopień 1. Wykres jest podawany przez funkcję obliczeniową wielomianową która zwraca poprzednika i …
1
Kiedy strategie -Nash Equilibrium zbiegają się ze strategiami Nash Equilibrium?
Równowagi Nasha ogólnie nie można obliczyć. -Nash równowaga jest zbiorem strategii, gdzie podane strategie rywalek, każdy gracz uzyska w ciągu maksymalnej możliwej oczekiwanego wypłat. Znalezienie równowagi Nash, biorąc pod uwagę i grę, jest .ϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonP P A DPPAD\mathsf{PPAD} Idąc ściśle za definicjami, wydaje się, że nie ma szczególnego powodu, aby sądzić, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.