Teoretyczne informatyka

2

Wykładnicze przyspieszenie w pamięci zewnętrznej

tło Pamięć zewnętrzna lub model DAM określa koszt algorytmu na podstawie liczby operacji we / wy, które wykonuje (w zasadzie liczby braków pamięci podręcznej). Te czasy działania są na ogół podawane w kategoriach , wielkości pamięci i B , liczby słów, które można jednocześnie przenieść do pamięci. Czasami L i …

15 ds.algorithms ds.data-structures cache-oblivious

1

Jak pokazać, że typ w systemie z typami zależnymi nie jest zamieszkały (tj. Formuła nie do udowodnienia)?

W przypadku systemów bez typów zależnych, takich jak system typu Hindley-Milner, typy odpowiadają formułom logiki intuicyjnej. Nie wiemy, że modele algebrami Heytinga, a w szczególności do zbicia wzór, można ograniczyć do jednego Heytinga Algebra gdzie każdy wzór jest reprezentowany przez otwarte podzestawu .RR\mathbb{R} Na przykład, jeśli chcemy pokazać, że nie …

15 lo.logic dependent-type model-theory calculus-of-constructions

4

Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem

Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej liczby ocen …

15 ds.algorithms lg.learning partial-order search-problem order-theory

3

Kombinatoryczna charakterystyka nauki ścisłej z zapytaniami członkowskimi

Edycja: Ponieważ od tygodnia nie otrzymałem żadnych odpowiedzi / komentarzy, chciałbym dodać, że cieszę się, że słyszę cokolwiek o problemie. Nie pracuję w okolicy, więc nawet jeśli jest to prosta obserwacja, mogę tego nie wiedzieć. Pomocny byłby nawet komentarz typu „Pracuję w okolicy, ale nie widziałem takiej charakterystyki”! Tło: Istnieje …

15 reference-request machine-learning lg.learning

4

Metoda wymuszania zastosowana w pracy relatywizacyjnej Bakera-Gilla-Solovaya i dowód hipotezy Cohena na temat ciągłości niezależności

Ogólnie interesuje mnie metoda wymuszania stosowana przez Baker-Gill-Solovay i Cohen. Szukam tak wielu źródeł, jak tylko mogę uzyskać informacje na temat samej techniki lub jej zastosowania. Czy ktoś ma jakieś sugestie?

15 cc.complexity-theory set-theory

3

pod względem

Probabilistyczny system zapobiegania jest powszechnie określany jako ograniczenie M A , gdy Arthur można wykorzystać tylko f ( n ) losowe fragmenty i może jedynie zbadanie g ( n ) bitów certyfikat potwierdzający przesłany przez Merlin (patrz: http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).P.doP.[ f( n ) , g( n ) ]P.doP.[fa(n),sol(n)]\mathcal{PCP}[f(n),g(n)]MM.ZA\mathcal{MA}fa( n )fa(n)f(n)sol( n …

15 cc.complexity-theory pcp interactive-proofs

1

Co możemy udowodnić za pomocą nieskończonych wykresów, że bez nich nie możemy udowodnić?

Jest to kontynuacja pytanie na ten temat nieskończonych wykresach. Odpowiedzi i komentarze do tego pytania zawierają listę obiektów i sytuacji, które są naturalnie modelowane przez nieskończone wykresy. Ale istnieją również liczne twierdzenia o grafach nieskończonych (patrz rozdział 8 w książce Diestela), z których na przykład bardzo popularny jest nieskończony lemat …

15 graph-theory co.combinatorics lo.logic

3

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 karabinów . W szczególności interesuje mnie odmiana przetasowania, która przekształca …

15 ds.algorithms time-complexity

1

Czy następujący problem NP jest trudny?

Rozważmy zbiór zbiorów F = { F 1 , F 2 , … , F n } nad zestawem podstawowym U = { e 1 , e 2 , … , e n } gdzie | F i | « N i e i ∈ F I i pozwolić K …

15 cc.complexity-theory np-hardness set-cover packing

1

Charakterystyka formuł jednorazowych na podstawie pełnej bazy binarnej

tło Formuła „read-once” na zbiorze bramek (zwana również podstawą) to formuła, w której każda zmienna wejściowa pojawia się jeden raz. Formuły do odczytu raz są powszechnie badane na podstawie De Morgana (która ma 2-bitowe bramki AND i OR oraz 1-bitową bramkę NOT) i pełnej bazy binarnej (która ma wszystkie 2-bitowe …

15 cc.complexity-theory circuit-complexity lower-bounds formulas

9

Jak stworzyć oprogramowanie krytyczne dla misji?

Uczę się metod formalnych. Słyszałem, że do tworzenia oprogramowania o kluczowym znaczeniu (takiego jak kontroler reaktora jądrowego, kontroler lotu statku powietrznego, kontroler sondy kosmicznej) stosuje się (i zwykle stosuje się) metody formalne. Dlatego chcę się tego nauczyć: str Jednak po zapoznaniu się z metodami formalnymi (zwłaszcza LTL, CTL i ich …

15 program-verification formal-methods se.software-engineering

1

Jak wydajne są solwery SAT oparte na DPLL w zadowalających instancjach PHP?

Wiemy, że DPLL oparte SAT-rozwiązują nie odpowie poprawnie na unsatisfiable wystąpień (zasada dziura gołąb), np na „nie jest injective mapowanie od n + 1 do n ”:P H PP.H.P.\mathrm{PHP}n + 1n+1n+1nnn P H Pn + 1n: = ⎛⎝⋀i ∈ [ n + 1 ] ⋁j ∈ [ n ] pja …

15 cc.complexity-theory lo.logic proof-complexity

1

Dwie macierze powiązane permutacją

Jaka jest złożoność obliczeniowa następującego problemu: dane dwie złożone macierzy i sprawdzają, czy istnieje macierz permutacji taka, że: B P B = P P T .n × nn×nn\times nZAZAAbbBP.P.PB = PA P.T..b=P.ZAP.T..B = P A P^T. Jeśli to pomoże, można założyć, że i są pustelnikami (lub nawet, że i są …

15 cc.complexity-theory np-hardness cg.comp-geom linear-algebra permutations

1

Niedoskonały izomorfizm subgrafu

Rozważmy następujący problem: Biorąc pod uwagę wykres zapytania i wykres odniesienia G ′ = ( V ′ , E ′ ) , chcemy znaleźć iniekcyjne odwzorowanie f : V → V ′, które minimalizuje liczbę krawędzi ( v 1 , v 2 ) ∈ E taki, że ( f ( …

15 cc.complexity-theory ds.algorithms graph-theory approximation-algorithms graph-isomorphism

2

Zastosowania quasi-PER / relacji dwufunkcyjnych / relacji zygzakowatych?

Biorąc pod uwagę zbiory i B , relacja difunkcyjna ( ∼ ) ⊆ A × B między nimi jest zdefiniowana jako relacja spełniająca następującą właściwość:AAABBB (∼)⊆A×B(∼)⊆A×B(\sim) \subseteq A \times B Jeżeli oraz a ′ ∼ b ′ i a ∼ b ′ , to a ′ ∼ b . a∼ba∼ba …

15 reference-request pl.programming-languages denotational-semantics logical-relations