Czytałem w SP Jordan D. Gosset "PJ Love -Complete problemów stoquastic Hamiltonians i macierzy MarkowaQ MZAQMAQMA ", że jest mało prawdopodobne, że .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM Byłem zaskoczony tym stwierdzeniem. Więc co jest właściwe relacje między i A M ?Q
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...
Razborov udowodnił, że każdy obwód monotoniczny, który oblicza idealną funkcję dopasowania dla grafów dwustronnych, musi mieć co najmniej bramek (nazwał to „logicznym stałym”). Czy od tego czasu udowodniono lepszą dolną granicę dla tego samego problemu? (powiedzmy 2 n ϵ ?) O ile pamiętam ten...
Istnieją 4 różne ograniczenia, które możemy mieć, definiując Losowy K-SAT. 1) Całkowita liczba literałów w danych klauzulach to dokładnie K lub AT, w większości K 2) Dany literał może być używany z lub bez zamiany w tej samej klauzuli (A lub A lub A) 3) Daną zmienną można użyć z lub bez zamiany w...
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...
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...
Rozważ następujący problem, Biorąc pod uwagę zestaw dodatnimi liczbami { 1 , ... , n } , w którym K ≥ 3 jest stała, chcemy podzielić wkomponowany m podzbiorów wielkości K , przy czym produkt z sumy każdego podzbioru jest zmaksymalizowane.n=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n...
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...
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(nlnn)O(n \ln n)O(n)O(n)O(n)Ω(nlnn)Ω(nlnn)\Omega(n \ln...
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 ) . Ta...
Wiemy, że jeśli wówczas całe PH załamuje się. Co się stanie, jeśli hierarchia wielomianowa ulegnie częściowemu zawaleniu? (Lub jak zrozumieć, że PH może spaść powyżej pewnego punktu, a nie poniżej?)P=NPP=NPP=NP Krótko mówiąc, jakie byłyby konsekwencje i P ≠ N P ?NP=coNPNP=coNPNP=coNPP≠NPP≠NPP\ne...
Unikalny SAT jest dobrze znanym problemem: biorąc pod uwagę wzór CNF , czy to prawda, że F ma dokładnie jeden model?FFFFFF Interesuje mnie problem «Dokładnie SAT»: biorąc pod uwagę wzór F CNF i liczbę całkowitą m > 1 , czy to prawda, że F ma dokładnie m modeli?mmmFFFm>1m>1m>1FFFmmm Oba...
Jakie są standardowe problemy, które możemy zredukować, aby udowodnić dolne granice ?Ω ( n logn )Ω(nlogn)\Omega(n\log n) Oczywiście problemy ze stanem inne niż sortowanie i rozróżnianie elementów.
Jak dobrze wiadomo, problemy optymalizacji trudne dla NP mogą mieć wiele różnych współczynników aproksymacji, począwszy od posiadania PTAS, aż do braku przybliżenia w ramach dowolnego czynnika. Pomiędzy nimi mamy różne stałe, , itp.p o l y ( n )O( logn )O(logn)O(\log n)po l y( n...
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...
Zwykle łatwiej jest uzasadnić rachunek różniczkowy, w którym ograniczeniem jest skończoność obliczeń, a nie próg taki jak „obliczalny w wielomianowym czasie”. Na przykład w teorii języków formalnych, zamiast używać aby scharakteryzować aperiodic monoïd, łatwiej jest używać profinite wyrazów, aby...
Powiedzmy, że mamy język , ale nie wiemy, jakie ciągi znaków są w rzeczywistości częścią tego języka. Wszystko, co ma, to skończony widok języka: skończony zestaw ciągów A \ subseteq L , o których wiadomo, że są w języku, oraz skończony zestaw ciągów B \ subseteq (\ Sigma ^ * \ setminus L), które...
Arora i Barak pokazują, że można wyrazić jako B P ⋅ N P, tj. Zestaw języków, w których losowe obniżki do 3SAT. M jest także naturalnym randomizowane uogólnienie N P w które zastąpi deterministyczny weryfikatora przez randomizowanym jeden.AMAM\mathsf{AM}BP⋅NPBP⋅NP\mathsf{BP}\cdot...
MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy...
Zdefiniuj „problem” jako algorytm akceptujący liczbę naturalną i zwracający 0 lub 1, która zwraca na co najmniej jednym . Każde takie nazywane jest „rozwiązaniem”AAA111n∈Nn∈Nn \in \mathbb{N}nnnAAA Zdefiniuj „uniwersalne narzędzie do rozwiązywania problemów” jako algorytm przyjmujący problem i...