Pytania otagowane jako cc.complexity-theory

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

1
Złożoność obwodu monotonicznego funkcji obliczeniowych na rzadkich wejściach
Wagaciągu binarnego to liczba jedynek w ciągu. Co się stanie, jeśli będziemy zainteresowani obliczeniem funkcji monotonicznej na wejściach z kilkoma?x ∈ { 0 , 1 } n| x ||x||x|x ∈ { 0 , 1 }nx∈{0,1}nx\in\{0,1\}^n Wiemy, że podjęcie decyzji, czy wykres ma klasę jest trudne dla obwodów monotonicznych (patrz między …
1
Wyrocznia, względem której
Zoologia złożoności autorstwa Grega Kuperberga stwierdza, że ​​istnieje język XXX taki, że BPPX⊈Δ2PXBPPX⊈Δ2PX\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X - innymi słowy, BPPX⊈PNPXBPPX⊈PNPX\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X} - ale nie podaje odniesienia do tego wyniku. Dlaczego tak się dzieje? Lub gdzie można znaleźć dowód? To pytanie jest częściowo uzasadnione moją odpowiedzią na pytanie „Co wiadomo …
1
Algorytm optymalnego sortowania w liczbie zamian
Biorąc pod uwagę ciąg liczb, czy można go sortować za pomocą porównań O ( n ln n ) i O ( n ) zamian / ruchów? Każdy wskaźnik do publikacji na ten temat lub kontrargumentów pokazujących dolną granicę Ω ( n ln n ) byłby pomocny.nnnO(nlnn)O(nln⁡n)O(n \ln n)O(n)O(n)O(n)Ω(nlnn)Ω(nln⁡n)\Omega(n \ln n)
2
PARITY
jest klasa układów wielomian wielkości stałej głębokości z nie bram i bezgranicznej fan-in i i lub bram, gdzie wejścia i bramy mają również nieograniczony Fanout.AC0AC0AC^0 Rozważmy teraz nową klasę, nazwijmy ją która jest jak A C 0, ale dla której wejścia i bramki mają co najwyżej O ( 1 ) …
2
Logika modalna aksjatyzowana z taką głębokością zagnieżdżenia, która raczej nie znajdzie się w PSPACE?
Szukam logiki modalnej, która jest aksjatyzowana przez skończony zestaw aksjomatów modalnej głębokości zagnieżdżenia, i których problem z zadowalalnością / pochodnością jest mało prawdopodobny w PSPACE. Bez ograniczenia modalnej głębokości zagnieżdżania nie stanowi to problemu, patrz na przykład PDL. Wydaje się jednak, że dowodząc na przykład twardości WYJĄTKOWEJ poprzez redukcję do …
3
Trudne problemy NP na kartografach
To pytanie jest podobne do trudnych NP problemów na drzewach : Istnieje duża liczba problemów z NP, które można rozwiązać na kartografach . Czy są jakieś znane problemy, które pozostają NP-kompletne, gdy są ograniczone do kartografów? Mówiąc ściślej, interesują mnie przykłady, w których dane wejściowe składają się wyłącznie z niekierowanego, …
1
Mierzenie losowości wzorów CNF
Powszechnie wiadomo, że formuły CNF można z grubsza podzielić na 2 szerokie klasy: losowe i strukturalne. Strukturalne formuły CNF, w przeciwieństwie do losowych formuł CNF, wykazują pewien porządek, pokazując wzorce, które prawdopodobnie nie wystąpią przypadkowo. Można jednak znaleźć formuły strukturalne wykazujące pewien stopień losowości (tzn. Niektóre określone grupy klauzul wydają …
2
Minimalne maksymalne rozwiązania LP
Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp. Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub równoważnie maksymalne minimalne rozwiązania? (To nie jest tak naprawdę pytanie badawcze, ale może możemy …
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.