Teoretyczne informatyka reference-request

1

„Informacje możliwe do zweryfikowania”: czy jest to znana koncepcja?

Poniższe wydaje mi się naturalną definicją i zastanawiam się, czy gdzieś to zbadano Rozważać X⊂2{0,1}∗X⊂2{0,1}∗\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}zestaw języków. NastępnieK⊂{0,1}ωK⊂{0,1}ωK \subset \lbrace 0, 1 \rbrace^\omega nazywa się "XX\mathsf{X}-weryfikowalne informacje ”, gdy są L∈XL∈XL \in \mathsf{X} św (i) Biorąc pod uwagę x∈Lx∈Lx \in L, każdy prefiks xxx jest w …

9 cc.complexity-theory reference-request

2

Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?

Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie. Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii .DTIME (2)n) ∪ DTIME (2)2)n) ∪ ⋯DTIME(2n)∪DTIME(22n)∪⋯\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) …

9 cc.complexity-theory reference-request complexity-classes computability

4

Treewidth i pakowanie

Moje pytanie jest trochę niejasne. Zastanawiam się, czy (i jak) możemy zastosować pojęcie szerokości do problemów z upakowaniem na wykresach. Byłbym zadowolony z wszelkich spostrzeżeń lub odniesień do wcześniejszych prac badawczych na ten temat (zakładając, że jest to jakaś relacja). Dzięki.

9 ds.algorithms reference-request graph-theory graph-algorithms approximation-algorithms

1

Funkcjonalna kompletność 3-wartościowej logiki

W kontekście niektórych ostatnich prac zdefiniowaliśmy język oparty na trójwartościowej logice à la Kleene, gdzie111 oznacza prawdę, 000 za fałsz i ⊥⊥\botza błąd lub nie wiem. Aby pokazać, że nasz język jest ekspresyjny, chcieliśmy udowodnić, że możemy zbudować zestaw funkcjonalnie kompletnych operatorów. Trudno było znaleźć istniejące wyniki w literaturze. Znaleźliśmy …

9 reference-request lo.logic

2

Złożoność komunikacji z sędzią

Załóżmy, że w strukturze złożoności komunikacyjnej mamy dwóch graczy A (wszy) i B (ob) i R (eferee). A i B nie komunikują się bezpośrednio ze sobą. W każdej rundzie komunikacji każda z nich wysyła wiadomość (mAmAm_A, mBmBm_B) do R. R oblicza dwie funkcje fA(mA,mB)fA(mA,mB)f_A(m_A,m_B) i fB(mA,mB)fB(mA,mB)f_B(m_A,m_B)i wysyła do nich wyniki. …

9 cc.complexity-theory reference-request communication-complexity

2

Obliczanie odległości do k-tego najbliższego sąsiada dla wszystkich punktów w zestawie

W przypadku aplikacji uczenia maszynowego moja grupa musi obliczyć odległość euklidesową do tego najbliższego sąsiada w zbiorze dla każdego (dla od 5 do około 100 oraz kilkaset do kilku milionów). Obecnie podejście albo oczywiste z drzewem kd na , które gdy jest wysokie, ajest stosunkowo niski, nigdy nie wygrywa. (Wszystko …

9 reference-request cg.comp-geom near-neighbors

1

Dowód, że najcięższe cięcie jest NP-twardy

Wszędzie, gdzie czytam o najrzadszym problemie cięcia, mówi tylko, że wiadomo, że jest to problem NP . Gdzie mogę znaleźć na to dowód? Który znany problem NP -twardości sprowadza się do najrzadszego problemu cięcia? Nie znalazłem żadnego dowodu w książce Vazirani - Algorytmy aproksymacji, która przedstawia algorytm Leightona Rao, ani …

9 cc.complexity-theory reference-request np-hardness

3

Rozwiązanie programowania liniowego w jednym przejściu z uporządkowanymi zmiennymi

Mam rodzinę problemów z programowaniem liniowym: maksymalizuj c′xdo′xc' x z zastrzeżeniem Ax≤bZAx≤bA x\le b, x≥0x≥0x\ge0. ElementyAZAA, bbb, i cdoc są liczbami całkowitymi nieujemnymi, cdocściśle pozytywne. (xxx powinien być również integralny, ale będę się tym martwić później). W mojej aplikacji często zdarza się, że współczynniki AAA i ccc są takie, że …

9 ds.algorithms reference-request linear-programming matrices

2

Punktem wyjścia dla algorytmów ignorowanych przez pamięć podręczną?

Interesuję się, gdy dowiaduję się więcej o algorytmach i strukturach danych nieobsługiwanych przez pamięć podręczną, ale jest tak wiele dokumentów, że tak naprawdę nie wiem od czego zacząć. Znalazłem oryginalną tezę Prokupa na ten temat, co wydaje się dobrym punktem wyjścia, ale jeśli istnieje proste i przystępne wprowadzenie do tematu, …

9 ds.algorithms reference-request cache-oblivious

2

Najkrótsze ścieżki uniemożliwiające każdą krawędź

Byłbym wdzięczny za wszelkie wskazówki lub warunki, które mogłyby doprowadzić mnie do właściwego kierunku. Mamy ukierunkowany wykres G = ( V, E)G=(V,E)G=(V,E) i długości lI jlijl_{ij} dla każdej krawędzi I jijijktóre można uznać za pozytywne. Istnieje specjalny węzeł początkowysss i węzeł końcowy ttt. Dla każdej krawędzi I jijij, chcielibyśmy obliczyć …

9 ds.algorithms reference-request graph-algorithms

1

Heurystyka dla optymalizacji

Ponieważ jest piątek, czas na pytanie CW. Szukam heurystyki, która ma szerokie zastosowanie w problemach związanych z optymalizacją. Aby ograniczyć zakres do bardziej „przyjaznej teorii” heurystyki, oto zasady (niektóre arbitralne, niektóre nie) Powinna to być dobrze zdefiniowana metoda bez wielu parametrów i z konkretnym czasem pracy (może na iterację) Powinny …

9 ds.algorithms reference-request optimization heuristics

2

Maksymalizacja sumarycznych wag krawędzi

Zastanawiam się, czy następujący problem ma nazwę lub wyniki z nim związane. Niech będzie wykresem ważonym, gdzie oznacza wagę krawędzi między i , a dla wszystkich , . Problem polega na znalezieniu podzbioru wierzchołków, który maksymalizuje sumę wag sąsiadujących z nimi krawędzi: Zauważ, że liczę krawędzie, które są wewnątrz podzbioru …

9 reference-request graph-theory approximation-algorithms terminology approximation-hardness

2

Informacje o k-SAT (wprowadzenie, ograniczenia, metody itp.)

Chciałbym wiedzieć, gdzie mogę się zwrócić o dobre, delikatne wprowadzenie do k-SAT (może to być dla matematyków, którzy nie mają dobrego przygotowania informatycznego). Chciałbym również znać artykuły, które mogą przeglądać lub wyjaśniać obecne metody rozwiązywania k-SAT. Wreszcie interesują mnie najbardziej znane metody rozwiązywania k-SAT. Chciałbym dowiedzieć się, jaki jest najlepszy …

9 reference-request sat survey

3

Algorytmy triangulacji wielokąta

Miałem trudności ze znalezieniem algorytmu lub opublikowaniem artykułów na temat triangulacji samoblokującego się wielokąta (również wielokąta o strukturze dziury). Czy ktoś może poprowadzić mnie do znalezienia opublikowanej pracy / algorytmu, proszę? PS: proszę odpowiednio oznaczyć to pytanie, nie mam wystarczającej liczby punktów reputacji, aby to zrobić.

9 ds.algorithms reference-request cg.comp-geom

1

Jakieś sformułowania SAT / SMT VRP / VRPTW (TSP, Job-Shop-Scheduling)?

zastanawiam się, czy są jakieś podejścia do formułowania problemu trasy pojazdu z systemem Windows-Time ( VRPTW ) (jako problemem decyzyjnym) jako instancji SAT / SMT? (alternatywnie: TSP) Na przykład: „Czy istnieje prawidłowe rozwiązanie odwiedzające wszystkich klientów w ich ramach czasowych przy n = 10 pojazdach?” Ten problem decyzyjny może być …

9 ds.algorithms reference-request sat reductions tsp

Pytania otagowane jako reference-request