Pytania otagowane jako descriptive-complexity

Złożoność opisowa klasyfikuje problemy na podstawie tego, jak trudno jest wyrazić problem w jakimś logicznym formalizmie.

5
Czy istnieje logika bez indukcji, która wychwytuje dużą część P?
Twierdzenie Immermana- Vardiego stwierdza, że ​​PTIME (lub P) to właśnie klasa języków, którą można opisać zdaniem logiki pierwszego rzędu wraz z operatorem punktu stałego, nad klasą uporządkowanych struktur. Operator punktu stałego może być albo najmniejszym punktem stałym (według Immermana i Vardiego), albo inflacyjnym punktem stałym. (Stephan Kreutzer, Ekspresyjna równoważność logiki …
2
Czy istnieją opisowe reprezentacje złożoności kwantowych klas złożoności?
Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany. Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można scharakteryzować za pomocą zapytań egzystencjalnych drugiego rzędu; P można scharakteryzować …
5
Dlaczego w ogóle działają relacyjne bazy danych, biorąc pod uwagę teoretyczną wykładniczą złożoność wyszukiwania odpowiedzi (w wielkości zapytania)?
Wydaje się znane, że aby znaleźć odpowiedź na zapytanie w relacyjnej bazie danych , potrzebny jest czas i nie można pozbyć się wykładnika.D | D | | Q | | Q |QQQrereD| D || Q ||re||Q||D|^{|Q|}| Q ||Q||Q| Ponieważ może być bardzo duży, zastanawiamy się, dlaczego bazy danych w ogóle …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
2
Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar S jest n …
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
1
Gry Ehrenfeucht-Fraïssé (w rzeczywistości Ajtai-Fagin) dla zwykłych języków.
Immerman (Complexity opisowa, 1999) przedstawia gry EF dla egzystencjalnej monadycznej drugiego rzędu (Gry Ajtai-Fagin) na stronie 127. Jak MSO na słowach jest odpowiednikiem zwykłych języków, gra może być napisany w sposób następujący.∃∃\exists Język jest regularny tylko wtedy, gdy Delilah nie ma strategii wygranej w następującej grze: 1. Samson wybiera , …
1
P i złożoność opisowa
W zoo o złożoności napisano [ 1 ], że w złożoności opisowej można zdefiniować za pomocą trzech różnych rodzajów wzorów, który jest również , a także jako .PPPFO(LFP)FO(LFP)FO(LFP)FO(nO(1))FO(nO(1))FO(n^{O(1)})SO(HORN)SO(HORN)SO(HORN) Istnieją jednak pewne wyjątki, na przykład nie może być wyrażona przez FP (FP ma taką samą moc ekspresji z LFP). i nie …
1
Na czym polegają twierdzenia o dychotomii?
Powszechnie wiadomo, że pewne klasy NP -Problemy Have dychotomia twierdzeń, które gwarantują, że każde zadanie w klasie jest albo NP -Complete lub jest w P . Najbardziej znanym takim wynikiem jest twierdzenie Schaefera o dychotomii wraz z szeregiem uogólnień. Rozumiem, że udowodnienie tych twierdzeń o dychotomii nie jest naprawdę łatwe. …
2
Kiedy właściwość FO zabija twardość NL?
Kontekst: Rozważamy tylko digrafy. Niech CYKL będzie językiem grafów z cyklem; jest to problem kompletny dla NL. Niech HASEDGE będzie językiem grafów z co najmniej jedną krawędzią. Zatem w sposób trywialny nie jest już trudny dla NL, podczas gdy zostaje.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE}CYCLE∪HASEDGE¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯CYCLE∪HASEDGE¯\text{CYCLE} \cup \overline{\text{HASEDGE}} Rzeczywisty problem: zastanawiam się, czy język …
1
Czy można zastosować opisową złożoną wersję twierdzenia Rice'a do oddzielenia AC0 i PSPACE?
W tym pytaniu wspomniano, że istnieją opisowe wersje złożoności twierdzenia Rice'a. Znalazłem dowód na następujące twierdzenie: Biorąc pod uwagę klasę złożoności C , nietrywialnych właściwości języków w C nie można obliczyć w C Wcześniej opublikowałem znaleziony dowód, ale ponieważ był on tak długi i ponieważ w komentarzach wskazano, że ten …
1
Skończona jednokierunkowa permutacja z nieskończoną domeną
Niech będzie permutacją. Zauważ, że chociaż działa w nieskończonej domenie, jego opis może być skończony. Przez opis rozumiem program, który opisuje funkcjonalność . (Jak w złożoności Kołmogorowa.) Zobacz wyjaśnienia poniżej. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^*ππ\piππ\pi Na przykład funkcja NOT jest jedną z takich permutacji: funkcja NOT (x) Niech y …
2
Jak możemy wyrazić „
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem wymiany stosów teoretycznych w informatyce. Zamknięte 7 lat temu . Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?P.= PS.P.A C.miP=PSPACEP=PSPACE Który poziom hierarchii arytmetycznej zawiera tę formułę (i …
2
Intuicja za systemami dowodowymi
Próbuję zrozumieć artykuł na temat p-Optimal Proof Systems and Logic for PTIME . W artykule jest pojęcie nazywane systemami dowodowymi i nie rozumiem intencji: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Identyfikujemy problemy z podzbiorami w .QQQΣ∗Σ∗\Sigma^* Myślę, że intencją jest to, że kodujemy pewną strukturę w …
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.