Pytania oznaczone «time-complexity»

16
podobne matryce

Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że...

15
Algorytm losowego ustawiania czasu w linijce w czasie

Czy istnieje algorytm tasowania karabinu liniowego w czasie? Jest to algorytm, który niektóre szczególnie sprawne ręce są w stanie wykonać: równomierne dzielenie tablicy wejściowej o równej wielkości, a następnie przeplatanie elementów dwóch połówek. Mathworld ma krótką stronę na temat losowania...

13
Rozróżnianie dwóch monet

Powszechnie wiadomo, że złożoność odróżnianie się stronniczy monetę z jednego sprawiedliwego jest θ ( ε - 2 ) . Czy istnieją wyniki dla odróżnienia monety p od monety p + ϵ ? Widzę, że dla specjalnego przypadku p = 0 złożoność będzie wynosić ϵ - 1 . Mam przeczucie, że złożoność będzie zależeć od...

12
Optymalne solwery NP

Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć...