Pytania otagowane jako disjoint-paths

0
Prosta ścieżka na sztyfcie z tylnymi krawędziami
Jaka jest złożoność następującego problemu ( P? NP-trudny?):∈∈\in Dane wejściowe: ukierunkowany wykres acykliczny , zestaw tylnych krawędzi E ′ ⊂ V × V i dwa odrębne węzły sD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsss i .ttt Pytanie: Niech oznacza wykres utworzony przez dodanie do D krawędzi od E ′ . Czy istnieje prosta ścieżka …
1
Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany
Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m …
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.