Teoretyczne informatyka

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

1
Dla których wykresów drzewo DFS jest zawsze ścieżką?
Dla których niekierowanych wykresów są wszystkie drzewa pierwszego wyszukiwania głębokości (dla wszystkich możliwych wierzchołków początkowych i dla wszystkich wyborów, których sąsiadów najpierw szukać) ścieżki skierowane? Oznacza to, że każde drzewo DFS powinno mieć tylko jeden liść, a każdy inny wierzchołek powinien mieć dokładnie jedno dziecko. Dotyczy to na przykład cykli, …
1
„Stopień trudności Rabina w obliczeniu funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”
Szukam: Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960 Streszczenie: „Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano pojęcie stopnia trudności obliczeń. Pojęcie to jest niezmienne w tym sensie, że jest niezależne od wyidealizowanych komputerów (maszyn …
4
Znalezienie najrzadszego rozwiązania układu równań liniowych
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …
3
Jakie są negatywne konsekwencje rozszerzenia CIC o aksjomaty?
Czy to prawda, że ​​dodanie aksjomatów do CIC może mieć negatywny wpływ na zawartość obliczeniową definicji i twierdzeń? I zrozumieć, że w normalnych zachowań teoria, wszelkie zamknięte termin zostanie zredukowany do kanonicznej normalnej postaci, na przykład w przypadku jest prawdziwy, wówczas n może obniżać się okres postaci ( s U …
2
Własność Churcha-Rossera dla rachunku lambda zależnie wpisanego?
Powszechnie wiadomo, że właściwość Church-Rosser obejmuje redukcję w prostym typie rachunku lambda. Oznacza to, że rachunek różniczkowy jest spójny w tym sensie, że nie wszystkie równania obejmujące terms można wyprowadzić: na przykład K I , ponieważ nie mają one tej samej postaci normalnej.λ ≠βηβη\beta \etaλλ\lambda≠≠\neq Wiadomo również, że wynik można …
1
W jaki sposób udowodniono, że MA wersji SETH jest fałszywa?
Zgodnie z tym artykułem , który omawia niedeterministyczne rozszerzenie hipotezy silnego czasu wykładniczego (SETH), „[…] Williams ostatnio wykazał, że podobne hipotezy dotyczące złożoności k-TAUT Merlina i Artura są fałszywe”. Jednak ten artykuł przytacza jedynie osobistą korespondencję. W jaki sposób udowodniono, że MA wersji SETH jest fałszywa? Podejrzewam, że wiąże się …
1
Najwolniejsza redukcja wielokrotna?
Gdy chcemy udowodnić, że jest N P -Complete, to standardowe podejście jest wykazują czasie wielomianowym obliczalny wiele-jeden redukcji znanego N P -Complete problemu do L . W tym kontekście nie potrzebujemy ścisłego ograniczenia czasu działania redukcji. Wystarczy mieć dowolne wiązanie wielomianowe, co może mieć bardzo wysoki stopień.L∈NPL∈NPL\in \bf NPNPNP\bf NPNPNP\bf …
2
Leksykograficznie minimalny rodzaj topologiczny oznaczonego DAG
Rozważmy problem, w którym jako dane wejściowe podajemy ukierunkowany wykres acykliczny , funkcję znakowania λ od V do jakiegoś zbioru L o całkowitej kolejności < L (np. Liczby całkowite) i gdzie jesteśmy proszeni o obliczyć leksykograficznie najmniejszy rodzaj topologiczny G pod względem λ . Dokładniej, A topologiczna sortowania z G …
2
Jaka jest równoważna definicja mP / poli w odniesieniu do maszyny Turinga?
P / poly to klasa problemów decyzyjnych rozwiązanych przez rodzinę obwodów boolowskich wielkości wielomianowych. Alternatywnie można go zdefiniować jako wielomianową maszynę Turinga, która otrzymuje ciąg porady, który jest wielomianem wielkości w n, i który opiera się wyłącznie na rozmiarze n. mP / poli to klasa problemów decyzyjnych rozwiązanych przez rodzinę …
2
Precyzja numeryczna w metodzie sumy kwadratów?
Czytałem trochę o metodzie sumy kwadratów (SOS) z badania Baraka i Steurera oraz notatek z wykładu Baraka . W obu przypadkach zamiatają pod dywan dywaniki o dokładności numerycznej. Z mojego (co prawda ograniczonego) zrozumienia tej metody powinny być spełnione następujące warunki: Biorąc pod uwagę dowolny układ równań wielomianowych EEE względem …
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.