Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

2
Informacje o uogólnionych grafach płaskich i uogólnionych grafach zewnętrznych płaszczyzn
Każdy płaski odpowiednio outerplanar wykres spełnia , odpowiednio | E ′ | ≤ 2 | V ′ | - 3 dla każdego podgrafu G ' = ( V ' , E ' ) z G . Również (zewnętrzne) wykresy płaskie można rozpoznać w czasie wielomianowym.G=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le 2|V'|-3G′=(V′,E′)G′=(V′,E′)G'=(V',E')GGG Co wiadomo na …
1
Czy istnieją warianty widocznych automatów przesuwających, które umożliwiają wypychanie słów na stos?
Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos. Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam cel.ϵϵ\epsilon Oczywiście, takie warianty mogą być tworzone, ale zastanawiam się, czy to rujnuje właściwości zamknięcia …
4
Sparametryzowany algorytm znajdowania biklików
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i sprawdzanie, czy występuje co najmniej k innych wierzchołków przypadających na wszystkie z …
1
Poszukuję oryginalnego papieru LCF Scotta
Czy następujący manuskrypt jest publicznie dostępny? Dana Scott, 1969, Teoria funkcji obliczeniowych wyższego typu . Niepublikowane notatki z seminarium, 7 stron, University of Oxford. Omówienie tego artykułu znajduje się w rozdziale 8.1.2, Typy jako zbiory , w Cardone i Hindley, 2006 Historia rachunku Lambda i logiki kombinatorycznej ; dodatkowo rozdział …
1
Jak nazywa się ten problem z grafem skierowanym?
Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.GGGv 2P.P.Pv1v1v_1v2)v2)v_2 Przykładem może być rozkład jazdy autobusów lub pociągów. Jeśli próbujesz ustalić …
1
Tautologie / sprzeczności średnich przypadków, poza przypadkowym modelem k-CNF
Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich (lub podwójnie w tautologiach, tj. Negacjach sprzeczności). Ten …
2
Znalezienie największego zestawu punktów o ograniczonej średnicy
Biorąc pod uwagę punkty w i odległość znajduję największy podzbiór tych punktów, tak że odległość euklidesowa nie jest większa niż .p1, … , Snp1,…,pnp_1,\ldots,p_nRreRre\mathbb{R}^{d}llllll Jaka jest złożoność tego problemu? Na wykresie nad punktami, które mają krawędź, ilekroć odległość dwóch punktów wynosi co najwyżej , problem jest równoznaczny ze znalezieniem maksymalnej …
2
Czy zaangażowanie bitowe daje nieświadomy transfer w modelu bezpieczeństwa opartym na teorii informacji?
Załóżmy, że masz dwóch arbitralnie silnych uczestników, którzy sobie nie ufają. Mają dostęp do bitowego zaangażowania (np. Zapieczętowane koperty zawierające dane, które jeden gracz może przekazać drugiemu, ale których nie można otworzyć, dopóki pierwszy gracz nie da drugiemu klucza). Czy możesz to wykorzystać do zbudowania nieświadomego protokołu przesyłania. Czy to …
1
Odniesienia do wykresów wolnych od (nieparzystych, dziurawych)?
Wykresy wolne od X to te, które nie zawierają wykresu z X jako indukowanego podgrupy. Otwór jest cykl co najmniej 4 wierzchołków. Odd-dziura jest dziura z nieparzystej liczby wierzchołków. Antihole jest dopełnieniem otworem. Wykresy wolne od (nieparzystej dziury, nieparzystej antihole) są dokładnie idealnymi grafami; to jest twierdzenie Strong Perfect Graph …
1
Odczyt na
Co powinienem przeczytać, aby zrozumieć ten problem? B Q P= B PP.B Q NdobQP.=bP.P.bQN.doBQP = BPP^{BQNC}B Q PbQP.BQPB P.P.B Q NdobP.P.bQN.doBPP^{BQNC}, ale pytanie brzmi, czy istnieje jakaś konkretna funkcja „inicjująca” taką wyrocznię. - Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html
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.