Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

3
Czy istnieje prosta gra o asymetrycznej złożoności?
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch …
1
Czy istnieje skończony jednolity zestaw bramek, który może dokładnie zrealizować wszystkie QFT rzędu
Rozważam pomysły dotyczące dokładnych algorytmów kwantowych. W szczególności rozważam prawdopodobne ograniczenia , które składa się z języków dokładnie określonych przez rodziny jednorodnych obwodów kwantowych o jednolitym czasie działania w dowolnym zestawie skończonych bramek.EQPEQP\mathsf{EQP} Kwantowa transformata Fouriera (QFT), dana przez jest znaną częścią kwantowej teorii obliczeniowej. W przypadku N = 2 …
2
Jak ocenić, czy definicja złożoności obliczeniowej rzeczywistych jest naturalna czy odpowiednia?
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w analizie obliczeniowej jest zgodny z modelem klasycznym, ale definicja złożoności obliczeniowej …
1
Wdrożenie drzew partycji?
Czy kiedykolwiek zaimplementowano drzewa partycji? Mówię tutaj o drzewach partycji z geometrii obliczeniowej. Najwcześniejsze (prawie) optymalne wersje były spowodowane przez Matouseka i innych, a ostatnio Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf To dla mnie szaleństwo, że nigdy nie zostały zaimplementowane, ale Google nie wykrył żadnych implementacji, o których nikt wcześniej nie donosił.
1
Zamieszanie na temat pokrycia wierzchołków zliczania redukcji do pokrycia cykli liczenia
To mnie dezorientuje. Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.PPP Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest -kompletny.#P#P\#P Dają one redukcję z liczenia okładek wierzchołków o rozmiarze do …
2
Dolna granica szacowania dla
Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .an≥⋯≥a1an≥⋯≥a1a_n \geq \dots\geq a_1ε∈(0,1)ε∈(0,1)\varepsilon \in (0,1)∑nk=1ak=1∑k=1nak=1\sum_{k=1}^n a_k = 1∑nk=1ak≤1−ε∑k=1nak≤1−ε\sum_{k=1}^n a_k \leq 1-\varepsilon Ile zapytań (wyszukiwań) jest wystarczających …
3
Implementacja surrealistycznych liczb do gier
Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub Wikipedię w celu wprowadzenia. Można je jeszcze …
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.