Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

1
Czy wszystkie znane algorytmy rozwiązywania problemów NP-zupełnych są konstruktywne?
Czy są znane algorytmy, które poprawnie wypisują odpowiedź „tak” dla problemu NP-complete bez pośredniego generowania certyfikatu? Rozumiem, że łatwo jest przekształcić wyrocznię spełniającą w znajdującą satysfakcjonujące zadanie: po prostu iteruj po zmiennych, za każdym razem pytając wyrocznię spełniającą o rozwiązanie związku tej zmiennej z pierwotnym problemem. Ale czy takie opakowanie …
2
Czy znalezienie rozwiązania problemu satysfakcji jest trudniejsze niż podjęcie decyzji o satysfakcji?
Czy problem polegający na ustaleniu, czy dane wyrażenie logiczne jest zadowalające obliczeniowo, różni się od znalezienia rozwiązania dla wyrażenia? Innymi słowy, czy istnieje inny sposób stwierdzenia, że ​​dane wyrażenie jest zadowalające bez wyraźnego określenia „właściwych ustawień” dla zmiennych boolowskich? Czy też wszystkie możliwe dowody skracają czas wielomianu do „właściwych ustawień”? …
1
Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?
Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady …
2
Najmniejszy DFA, który akceptuje podane ciągi i odrzuca inne podane ciągi
Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem Σ , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) M taki, że A ⊆ L ( M ) i L ( M ) ⊆ Σ ∗ ∖ BA,BA,BA,BΣΣ\SigmaMMMA⊆L(M)A⊆L(M)A \subseteq L(M)L(M)⊆Σ∗∖BL(M)⊆Σ∗∖BL(M) \subseteq \Sigma^*\setminus B ? Innymi słowy, reprezentuje zestaw pozytywnych przykładów. …
2
Wszechświaty w teorii typów zależnych
Czytam o teorii typów zależnych w książce online The Homotopy Type Theory . W sekcji 1.3 rozdziału Teoria typów wprowadza pojęcie hierarchii wszechświatów : , gdzieU0:U1:U2:⋯U0:U1:U2:⋯\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots każdy wszechświat jest elementem następnego wszechświata . Ponadto zakładamy, że nasze wszechświaty są kumulatywne, to znaczy, że wszystkie …
1
Jaki jest kompaktowy sposób reprezentowania partycji zestawu?
Istnieją wydajne struktury danych do reprezentowania ustawionych partycji. Te struktury danych charakteryzują się dużą złożonością czasową dla operacji takich jak Union i Find, ale nie są szczególnie efektywne pod względem przestrzeni. Jaki jest oszczędny przestrzennie sposób reprezentowania partycji zestawu? Oto jeden z możliwych punktów wyjścia: Wiem, że liczba partycji zestawu …
3
Różnica między krawędziami poprzecznymi i przednimi w DFT
W pierwszym drzewie głębokości znajdują się krawędzie, które definiują drzewo (tj. Krawędzie, które zostały użyte podczas przejścia). Pozostały pewne krawędzie łączące niektóre inne węzły. Jaka jest różnica między krawędzią poprzeczną a przednią? Z wikipedii: Na podstawie tego drzewa łączącego krawędzie oryginalnego wykresu można podzielić na trzy klasy: krawędzie przednie, które …
1
Pompujący lemat dla deterministycznych języków bezkontekstowych?
Lemat pompujący dla zwykłych języków może być użyty do udowodnienia, że ​​niektóre języki nie są regularne, a lemat pompujący dla języków bezkontekstowych (wraz z lematem Ogdena) może być użyty do udowodnienia, że ​​niektóre języki nie są kontekstowe. Czy istnieje determinujący lemat dla deterministycznych języków bezkontekstowych? To znaczy, czy istnieje lemat …
1
Zwięzły przykład wykładniczego kosztu wnioskowania typu ML
Zwrócono mi uwagę, że koszt wnioskowania o typ w funkcjonalnym języku, takim jak OCaml, może być bardzo wysoki. Twierdzenie jest takie, że istnieje ciąg wyrażeń taki, że dla każdego wyrażenia długość odpowiedniego typu jest wykładnicza względem długości wyrażenia. Wymyśliłem sekwencję poniżej. Moje pytanie brzmi: czy znasz sekwencję z bardziej zwięzłymi …
2
Dlaczego problemy decyzyjne są powszechnie stosowane w teorii złożoności?
Z Wikipedii : Rodzaj problemu obliczeniowego: Najczęściej stosowanymi problemami są problemy decyzyjne . Klasy złożoności można jednak zdefiniować na podstawie problemów z funkcjami, problemów z liczeniem, problemów z optymalizacją, problemów z obietnicą itp. Widziałem także definicje NP-zupełne, NP-twarde, NP, ..., zdefiniowane tylko dla problemów decyzyjnych. Zastanawiam się, dlaczego tak jest? …
2
Jeśli A mapuje się redukowalnie do B, to dopełniacz A jest mapowalny redukowalny do dopełniacza B
Studiuję do finałowej teorii obliczeń i walczę z właściwym sposobem odpowiedzi na pytanie, czy to stwierdzenie jest prawdziwe w odniesieniu do fałszu. Przez definicję z możemy skonstruować następujące oświadczenie,≤m≤m\leq_m w ∈ A⟺fa( w ) ∈ B → w ∉ A⟺fa( w ) ∉ Bw∈A⟺f(w)∈B→w∉A⟺f(w)∉Bw \in A \iff f(w) \in B …
2
Czy możemy pokazać, że języka nie da się wyliczyć, pokazując, że nie ma dla niego weryfikatora?
Jedna z definicji zestawu wyliczalnego (ce, równoważnego rekurencyjnie wyliczalnemu, równoważnego semidecidable) jest następująca: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* oznacza, że ​​istnieje rozstrzygalny językV⊆Σ∗V⊆Σ∗V\subseteq \Sigma^* (zwany weryfikatorem) st dla wszystkichx∈Σ∗x∈Σ∗x\in \Sigma^* , IFF istnieje y ∈ Ď * st ⟨ x , y ⟩ ∈ V .x∈Ax∈Ax\in Ay∈Σ∗y∈Σ∗y\in\Sigma^*⟨x,y⟩∈V⟨x,y⟩∈V\langle x, y \rangle \in V …
3
Pojęcia wydajnego obliczenia
Algorytm maszyny Turinga w czasie wielomianowym jest uważany za wydajny, jeśli jego czas działania, w najgorszym przypadku, jest ograniczony przez funkcję wielomianu w wielkości wejściowej. Mam świadomość silnej tezy Kościoła-Turinga: Każdy rozsądny model obliczeń może być skutecznie symulowany na maszynach Turinga Nie znam jednak solidnej teorii do analizy złożoności obliczeniowej …
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.