Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

1
Złożoność rozpoznawania grafów przechodnich werteksów
Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik. Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla wierzchołków?GGGnnnnnnGGG Przypomnij sobie, że wykres jest przechodni na wierzchołki, jeśli działa …
2
Charakterystyka problemów, dla których istnieją algorytmy czasu podliniowego
Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń podliniowa (np. Algorytmy szkicowania / przesyłania strumieniowego, w których maszyna Turinga ma taśmę tylko do odczytu, podliniową przestrzeń …
1
Twardość NP problemu podziału grafu?
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i .EEEE1E1E_1E2E2E_2V1V1V_1V2V2V_2E1∪E2=EE1∪E2=EE1∪E2=EV1∪V2=VV1∪V2=VV1∪V2=V Ten problem jest co najmniej tak trudny jak problem z …
1
Gramatyka kontekstowa dla SAT?
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem dla księgowości. Oznacza to, że SAT musi mieć …
2
Liczba bramek binarnych potrzebnych do obliczenia AND i OR n bitów wejściowych jednocześnie
Jaka jest minimalna liczba bramek binarnych potrzebnych do jednoczesnego obliczenia AND i OR bitów wejściowych? Trywialna górna granica wynosi 2 n - 2 . Uważam, że jest to optymalne, ale jak to udowodnić? Nie działa tutaj standardowa technika eliminacji bramki, ponieważ poprzez przypisanie stałej do dowolnej zmiennej wejściowej trywializuje jedno …
2
Czy jest jakiś problem w
ΣP2Σ2P\mathsf{\Sigma^P_2}PP\mathsf{P} na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich rozwiązania.
1
Czy możesz zdecydować o równoważności monotonicznych wyrażeń boolowskich, które nie zawierają negacji w PTIME?
Czy następujący problem występuje w trybie PTIME lub coNP-hard: Biorąc pod uwagę dwa wyrażenia logiczne i w zmiennyche1e1e_1e2e2e_2 , bez negacji (tzn. Wyrażenia są w całości budowane przez ∧ i ∨ ). Zdecyduj, czy e 1 ≡ e 2 , czyli mają taką samą wartość dla wszystkich przypisań do zmiennych.x1,…,xnx1,…,xnx_1,\dots,x_n∧∧\wedge∨∨\veee1≡e2e1≡e2e_1 …
2
Paradygmaty analizy złożoności algorytmów
Analiza najgorszych i średnich przypadków to dobrze znane miary złożoności algorytmu. Niedawno wygładzona analiza pojawiła się jako kolejny paradygmat wyjaśniający, dlaczego niektóre algorytmy wykładnicze w najgorszym przypadku działają tak dobrze w praktyce, na przykład algorytm simpleksowy. Moje pytanie brzmi - czy istnieją jakieś inne paradygmaty do pomiaru złożoności algorytmu? Szczególnie …
1
Skuteczne połączenie DFA?
Istnieją teoretyczne dowody na to, że naiwna konstrukcja produktu kartezjańskiego na przecięciu DFA jest „najlepsza, co możemy zrobić”. Co z konkatenacją dwóch DFA? Trywialna konstrukcja polega na przekształceniu każdego DFA w NFA, dodaniu przejścia epsilon i określeniu wynikowego NFA. Czy możemy zrobić lepiej? Czy znane jest ograniczenie wielkości minimalnej DFA …
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 …
5
Czy „Funkcje jednokierunkowe” mają jakieś aplikacje poza kryptografią?
Funkcja jest jednokierunkowa, jeśli f można obliczyć za pomocą algorytmu wielomianowego czasu, ale dla każdego losowego algorytmu wielomianowego czasu A ,f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^*fffAAA Pr[f(A(f(x)))=f(x)]&lt;1/p(n)Pr[f(A(f(x)))=f(x)]&lt;1/p(n)\Pr[f(A(f(x))) = f(x)] < 1/p(n) dla każdego wielomianu i wystarczająco dużego n , przy założeniu, że x jest wybrany równomiernie z { 0 …
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.