Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

1
Problem decyzyjny taki, że dowolny algorytm dopuszcza wykładniczo szybszy algorytm
W Hromkovič's Algorytmics for Hard Problems (2nd edition) znajduje się takie twierdzenie (2.3.3.3, strona 117): Istnieje (rozstrzygalny) problem decyzyjny taki że dla każdego algorytmu A, który rozwiązuje P, istnieje inny algorytm A ', który również rozwiązuje P i dodatkowo spełniaP.PPZAAAP.PPA′A′A'PPP ∀∞n∈N.TimeA′(n)=log2TimeA(n)∀∞n∈N.TimeA′(n)=log2⁡TimeA(n)\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n) jest …
1
Łatwa redukcja z 3SAT do problemu ścieżki Hamiltonian
W książce Sipsera „Wprowadzenie do teorii obliczeń” na stronie 286 zmniejszono z 3SAT do problemu ścieżki Hamiltona. Czy istnieje prostsza redukcja? Mówiąc prościej, mam na myśli redukcję, która byłaby łatwiejsza do zrozumienia (dla studentów). Czy istnieje redukcja wykorzystująca liniową liczbę zmiennych? Redukcja w Sipserze wykorzystuje zmienne , gdzie jest liczbą …
1
Wydajne obliczanie lub przybliżanie wymiaru VC sieci neuronowej
Moim celem jest rozwiązanie następującego problemu, który opisałem na podstawie jego danych wejściowych i wyjściowych: Wejście: Kierunkowy wykres acykliczny z m węzłami, n źródłami i 1 ujściem ( m > n ≥ 1 ).GGGmmmnnn111m>n≥1m>n≥1m > n \geq 1 Wynik: VC wymiar (lub zbliżanie niego) dla sieci neuronowej z topologii .GGG …
1
Czy minimalne cięcie może być łatwiejsze niż przepływ sieci?
Dzięki twierdzeniu o maksymalnym przepływie min-cut wiemy, że możemy użyć dowolnego algorytmu do obliczenia maksymalnego przepływu na grafie sieciowym do obliczenia -min-cut. Dlatego złożoność obliczenia minimum -cięcie jest nie większa niż złożoność obliczenia przepływu maksymalnego .( s , t )(s,t)(s,t)(s , t )(s,t)(s,t)(s , t )(s,t)(s,t) Czy może być mniej? …
1
Czy układanki „zero-jedynkowe” są kompletne NP?
Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka to ˉ k , dla niektórych k ∈ …
2
Redukcja wielomianu z dowolnego problemu NP-zupełnego do ograniczonego PCP
Podręczniki wszędzie założyć, że Bounded post Korespondencja Problem jest NP-zupełny (nie więcej niż NN.N indeksy dozwolony z powtórzeń). Nigdzie jednak nie pokazano prostej (jak w czymś, co student może zrozumieć) wielomianowej redukcji czasu z innego problemu pełnego NP. Jednak każda redukcja, o której mogę myśleć, ma charakter wykładniczy (według NN.N …
1
Udowodnienie (nie) wykonalności tego N-tego pierwszego wznowienia
Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi. Krótko mówiąc, możemy zdefiniować odstęp między każdą liczbą pierwszą jako powtórzenie …
4
Pokazuje, że problem w X nie jest X-Complete
Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić? Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład …
5
Jak udowodnić, że problem NIE jest NP-Complete?
Czy istnieje jakaś ogólna technika dla udowodnienia, że ​​problem NIE jest NP-Complete? Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P. Oczywiście nie jest to prawdziwa odpowiedź. NP-Complete jest …
3
Czy istnieje pogląd na złożoność twierdzenia Galois?
Twierdzenie Galois skutecznie mówi, że nie można wyrazić pierwiastków wielomianu stopnia> = 5 za pomocą racjonalnych funkcji współczynników i rodników - czy nie można tego odczytać, mówiąc, że biorąc pod uwagę wielomian, nie ma deterministycznego algorytmu znajdowania pierwiastków? Zastanówmy się teraz nad pytaniem o formę: „Biorąc pod uwagę prawdziwy zakorzeniony …
2
Gęsty NP pełny język oznacza P = NP
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in \mathbb{N}.nnnnnnJ.jot.J. Problem, który obecnie badam, wymaga przedstawienia następujących informacji Jeśli istnieje gęsty język , …
1
Uniwersalna symulacja maszyn Turinga
Niech będzie stałą funkcją konstruowaną w czasie.fff Klasyczny uniwersalny wynik symulacji dla TM (Hennie i Stearns, 1966) stwierdza, że ​​istnieje TM z dwiema taśmami, takaUUU opis TM i⟨M⟩⟨M⟩\langle M \rangle ciąg wejściowy ,xxx uruchamia kroki i zwraca odpowiedź na . I może być dowolną funkcją w .g(|x|)g(|x|)g(|x|)MMMxxxgggω(f(n)lgf(n))ω(f(n)lg⁡f(n))\omega(f(n)\lg f(n)) Moje pytania …
1
Czy asymptotyczne dolne granice są istotne dla kryptografii?
Ogólnie uważa się, że asymptotyczna dolna granica, taka jak twardość wykładnicza, sugeruje, że problem jest „z natury trudny”. Uważa się, że szyfrowanie „z natury trudne do złamania” jest bezpieczne. Jednak asymptotyczna dolna granica nie wyklucza możliwości, że ogromna, ale skończona klasa wystąpień problemów jest łatwa (np. Wszystkie wystąpienia o rozmiarze …
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.