Pytania otagowane jako cc.complexity-theory

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

1
Znaczenie P = NP? zależy od geometrii czasoprzestrzennej?
To pytanie dotyczy strony 125 książki „Automaty komórkowe w przestrzeniach hiperbolicznych: tom 2” Maurice Margenstern, Archiwa wydawców współczesnych, 2008. http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125 Zdaniem autora pytanie P = NP jest źle postawione, ponieważ w ustawieniu hiperbolicznym P = NP lub w notacji używanej później w książce P h = NP h . Nie …
1
Złożoność heksów z losową kolejnością tur.
Myślałem o wariancie heksowym , w którym zamiast dwóch graczy wykonujących ruchy na przemian, każda kolej losowo wybrana przez gracza wykonuje ruch. Jak trudno jest określić szanse wygranej każdego gracza? Ten problem występuje oczywiście w PSPACE, ale nie może być trudny do NP, a tym bardziej kompletny w PSPACE. Trudności …
3
Twardość UGC predykatu
Tło : W oryginalnym dokumencie UGC Subhash Khota ( PDF ) udowadnia trudność UG w podejmowaniu decyzji, czy dana instancja CSP z ograniczeniami w całej formie Niezupełna (a, b, c) w stosunku do trójskładnikowego alfabetu przyznaje zadanie spełniające 1 - ograniczeń lub czy nie ma zadowalających zadań 8ϵϵ\epsilonograniczeń, dla dowolnie …
1
Czy możemy zdecydować, czy stały ma unikalny termin?
Załóżmy, że otrzymujemy macierz n przez n, M, z wpisami liczb całkowitych. Czy możemy zdecydować w P, czy istnieje permutacjaσσ\sigma taka, że ​​dla wszystkich permutacji mamy ?π≠ σπ≠σ\pi\ne\sigmaΠ Mi σ( i )≠ Õ Mi π( i )ΠM.jaσ(ja)≠ΠM.jaπ(ja)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Uwagi Oczywiście można wymienić produkt na sumę, problem pozostaje ten …
5
Silniejsze pojęcia ujednolicenia?
Jedną z luk, o której zawsze zdawałem sobie sprawę, że tak naprawdę nie rozumiem, jest między niejednorodną i jednolitą złożonością obliczeniową, gdzie złożoność obwodu reprezentuje niejednorodną wersję, a maszyny Turinga to, że rzeczy są jednolite. Przypuszczam, że „jednolity” jest sposobem na ograniczenie klasy algorytmów, np. Niedopuszczenie zupełnie innego obwodu dla …
3
Które problemy
Słynny obraz świata Neila Immermana jest następujący (kliknij, aby powiększyć): Jego „Naprawdę wykonalna” klasa nie obejmuje żadnej innej klasy; moje pytanie brzmi: Co to jest problem AC 0, który jest uważany za niepraktyczny i dlaczego?
1
Wyraźne separacje między obwodami kwantowymi o głębokości poli- i logarytmicznej
Następujący problem pojawia się na liście Aaronsona Dziesięć pół-wielkich wyzwań dla teorii obliczeń kwantowych . Jest B Q P = B P PB Q N CbQP.=bP.P.bQN.do\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} Innymi słowy, i „kwantową” część dowolnego algorytmu kwantowej być skompresowane do p o l y l o g (n)polylosol(n)\mathrm{polylog}(n) głębokości, pod warunkiem, że jesteśmy …
1
Problemy z logDCFL-complete
LogCFL to zestaw wszystkich języków, które można sprowadzać do przestrzeni logicznej do języka bezkontekstowego. Podobnie LogDCFL jest zbiorem wszystkich języków, które są przestrzenią logiczną redukowalną do deterministycznego języka bezkontekstowego. Zobacz ten artykuł na Wikipedii, aby zapoznać się z niektórymi naturalnymi problemami związanymi z logCFL. Istnieje kilka innych interesujących problemów z …
1
Odczyt na
Co powinienem przeczytać, aby zrozumieć ten problem? B Q P= B PP.B Q NdobQP.=bP.P.bQN.doBQP = BPP^{BQNC}B Q PbQP.BQPB P.P.B Q NdobP.P.bQN.doBPP^{BQNC}, ale pytanie brzmi, czy istnieje jakaś konkretna funkcja „inicjująca” taką wyrocznię. - Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html
1
Podziel wykres na cykle rozłączne węzłów
Powiązany problem: Twierdzenie Veblena stwierdza, że ​​„Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy każdy wierzchołek ma równy stopień”. Mój problem: …
1
Czy ?
Oczekuję, że odpowiedź brzmi „nie”, ale tak naprawdę nie mogłem skonstruować kontrprzykładu. Różnica polega na tym, że w ∩ ε > 0 D T I M E ( O ( n 2 + ε ) )∩ε>0DTIME(O(n2+ε))∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) możemy nie być w stanie wybrać algorytmu O ( n 2 + ε …
3
Ilościowe formuły logiczne z logarytmicznymi przemianami
Badam problem, który jest trudny dla klasy skwantyfikowanych formuł boolowskich z logarytmiczną liczbą zmian kwantyfikatorów. Problem w tej klasie wyglądałby następująco: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalog⁡n−1,…xalog⁡n)F\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots x_{a_2}), \ldots \exists(x_{a_{\log n - 1}}, \ldots x_{a_{\log n}})F Gdzie log n = N , a M jest wartością logiczną wzór …
3
Przykłady udanej derandomizacji z BPP na P.
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet w tym przypadku istniała metodologia zakładająca GRH). Więc jakie konkretne dowody na przykładzie …
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.