Teoretyczne informatyka

2

Odniesienia do języków programowania opartych na logice warunkowej

Logiki warunkowe to logiki, które rozszerzają tradycyjną implikację logiczną za pomocą operatorów modalnych odpowiadających innym pojęciom warunku (na przykład przyczynowy warunkowy brzmi „ powoduje„ B ”lub warunkowanie probabilistyczne „ ”, które brzmi „ dany B ”).A A | B AA□→BA◻→BA\; \square\!\!\!\!\to BAAAA|BA|BA|BAAABBB Zazwyczaj logiki te są badane teoretycznie modelowo, ale …

11 reference-request lo.logic pl.programming-languages type-theory proof-theory

3

Regularne wykresy i izomorfizm

Chciałbym zapytać, czy jest na to już opublikowany wynik: Bierzemy wszystkie możliwe różne ścieżki między każdą parą węzłów dwóch połączonych regularnych (o powiedzmy stopnia , i liczby węzłów ) wykresów i zapisujemy ich długości. Oczywiście ta liczba odrębnych ścieżek ma charakter wykładniczy. Moje pytanie brzmi: jeśli posortujemy długości i porównamy …

11 graph-theory co.combinatorics graph-algorithms graph-isomorphism

4

Znalezienie skończonego modelu

Wiem, że pytanie „czy formuła pierwszego rzędu ma model” jest ogólnie nierozstrzygalne.ϕϕ\phi Czy ktoś mógłby mi dać link lub książkę, która da odpowiedź na skończone modele. Jeśli mam wzór pierwszego rzędu , czy można rozstrzygnąć, czy ϕ ma model skończony? Jestem pewien, że pytanie jest dobrze znane, ale nawet nie …

11 reference-request lo.logic computability finite-model-theory

1

Jaka jest złożoność (być może zwięzłego) Nurikabe?

Nurikabe to układanka wypełniająca siatki oparta na ograniczeniach, luźno podobna do Saperów / Nonogramów; liczby są umieszczane na siatce, która ma być wypełniona wartościami włączania / wyłączania dla każdej komórki, przy czym każda liczba wskazuje region połączonych komórek „on” o tej wielkości, a także pewne drobne ograniczenia w obszarze komórek …

11 cc.complexity-theory np-hardness puzzles

1

Złożoność przestrzeni dla średnich przypadków

Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić …

11 cc.complexity-theory reference-request space-bounded average-case-complexity

4

Klasa złożoności NEXP

Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne problemy niż ogólne (biorąc …

11 cc.complexity-theory reference-request complexity-classes nexp

1

Czy semantyczna metryka Escardó dla limitów czasu PCF + jest w pełni abstrakcyjna?

W swoim artykule warsztatowym z 1999 r. „Metryczny model PCF” Martín Escardó wykazał, że można podać prostą interpretację PCF w kategorii kompletnych przestrzeni ultradźwiękowych i nie ekspansywnych map. Pokazał, że ten model jest odpowiedni i że może modelować dodanie konstrukcji limitu czasu (tj. Operatora, który uruchomiłby swój argument dla pewnej …

11 pl.programming-languages denotational-semantics metric-spaces

1

Stan badań nad atakami zderzeniowymi SHA-1

Bezpieczeństwo SHA-1 zostało omówione, ponieważ algorytm znajdowania kolizji został po raz pierwszy opublikowany w CRYPTO 2004, a następnie został ulepszony. Wikipedia wymienia kilka odniesień , jednak wydaje się, że najnowsze badania opublikowane (a później wycofane) na ten temat miały miejsce w 2009 r. (Cameron McDonald, Philip Hawkes i Josef Pieprzyk …

11 cr.crypto-security hash-function cryptographic-attack

2

Jakieś klasy hipotez inne niż parzystość w hałaśliwym PAC, ale nie w SQ?

Angluin i Laird ('88) sformalizowali uczenie się z przypadkowo uszkodzonymi danymi w modelu „PAC z losowym szumem klasyfikacyjnym” (lub hałaśliwym PAC). Model ten jest podobny do PAC uczenia , z wyjątkiem etykiet z przykładów podanych w uczącej są uszkodzone (grzbiet), niezależnie w sposób losowy, z prawdopodobieństwem .η<1/2η<1/2\eta < 1/2 Aby …

11 lg.learning

6

Zastosowanie teorii grafów w informatyce

Jestem studentką CS. Zrobiliśmy teorię grafów w jednym kursie. Uważam to za interesujące. Jakie są prawdziwe zastosowania teorii grafów w dziedzinie informatyki? Na przykład odkryłem, że niektóre koncepcje teorii grafów można wykorzystać do projektowania sieci. Jakie są inne podobne aplikacje?

11 graph-theory co.combinatorics big-list application-of-theory

3

Czy Merlin może przekonać Artura o określonej kwocie?

Merlin, który ma nieograniczone zasoby obliczeniowe, chce przekonać Arturowi, że m | ∑p ≤ N, p pierwsza pkm|∑p≤N., p głównypkm|\sum_{p\le N,\ p\text{ prime}}p^k dla ( N, m , k )(N.,m,k)(N,m,k) przy k = O ( logN.)k=O(log⁡N.)k=O(\log N) i m = O ( N) .m=O(N.).m=O(N). Obliczenie tej sumy w prosty sposób …

11 cc.complexity-theory ds.algorithms time-complexity interactive-proofs nt.number-theory

1

Minimalna waga lasy o podanej liczności

To pytanie było motywowane pytaniem dotyczącym przepływu stosu . Załóżmy, że otrzymujesz zrootowane drzewo (tzn. Jest to root, a węzły mają dzieci itp.) W węzłach (oznaczonych ).n 1 , 2 , … , nT.T.Tnnn1 , 2 , … , n1,2),…,n1, 2, \dots, n Każdy wierzchołek ma powiązaną nieujemną masę całkowitą: …

11 cc.complexity-theory reference-request np-hardness tree application-of-theory

1

Zwiększanie konkurencyjności solverów SAT dzięki wyspecjalizowanym algorytmom

Jakie są przeszkody w konkurowaniu solverów SAT ze specjalistycznymi algorytmami graficznymi? Innymi słowy, czy jest możliwe oczekiwanie od solverów SAT, które mogą zastąpić rolę projektanta algorytmów - tj. Być w stanie automatycznie rozpoznać strukturę problemu, a następnie rozwiązać go tak szybko, jak specjalistyczny algorytm? Oto kilka przykładów, które moim zdaniem …

11 ds.algorithms graph-theory sat

1

Czy istnieją „refleksyjne” algorytmy mieszające?

Czy istnieje klasa algorytmów mieszających, teoretycznych lub praktycznych, tak że algorytm w tej klasie można uznać za „zwrotny” zgodnie z definicją podaną poniżej: hash1 = algo1 („tekst wejściowy 1”) hash1 = algo1 („tekst wejściowy 1” + hash1) Operator + może być konkatenacją lub dowolną inną określoną operacją, aby połączyć wynik …

11 ds.algorithms hash-function

1

Dlaczego problemy z uzupełnianiem NP nie mają podobnych współczynników aproksymacji?

Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że pewne stałe lub nawet wielomianowe znoszenie może być zrozumiane, ale …

11 cc.complexity-theory approximation-algorithms reductions