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 …
Zadałem to pytanie kilka tygodni temu w Mathoverflow , ale nie otrzymałem odpowiedzi. Tutaj przez siatkę 3D długości bocznej rozumiem wykres G = ( V , E ) z V = { 1 , … , k } 3 i E = { ( ( a , b , c …
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 MZAQMAQMAMAMAM
Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k kk∈Nk∈Nk\in\mathbb{N}GkGkG_kkkkG0G0G_0GkGkG_kkkk Drugi kierunek oczywiście …
Rozkład drzew jest trudny w najgorszym przypadku, ale chciwa metoda wydaje się być prawie optymalna w małych rzeczywistych sieciach. Czy coś wiadomo o twardości rozkładu drzewa „typowego” wystąpienia jakiejś klasy grafów? Czy istnieje przykład rodziny grafów, w której chciwe metody rozkładu drzew źle się sprawdzają?
Szukam nazwy lub jakichkolwiek odniesień do tego problemu. Biorąc pod uwagę wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) znajdź podział wierzchołków na n=|V|n=|V|n = |V|ustawia S1,…,SnS1,…,SnS_1,\ldots,S_n tak, aby zmaksymalizować wartość przyciętych krawędzi: c(S1,…,Sn)=∑i≠j⎛⎝∑(u,v)∈E:u∈Si,v∈Sjw(u,v)⎞⎠c(S1,…,Sn)=∑i≠j(∑(u,v)∈E:u∈Si,v∈Sjw(u,v))c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right) Zauważ, że niektóre zestawySiSiS_imogą być …
Jakie są problemy z najlepiej znanym współczynnikiem aproksymacji osiągniętym przez algorytm zwracający jednolicie losowe rozwiązanie? Znam jeden taki przykład problemu : w artykule „ Tight Bounds for Permutation Flow Shop Scheduling ” Viswanath Nagarajan i Maxim Sviridenko udowodnili, że losowa sekwencja zadań ma gwarancję 2 √fa| perm | dom a …
Niech G będzie połączonym wykresem. Jaka jest złożoność zliczania wszystkich połączonych podgrafów, jeśli G jest następujących typów? G jest ogólny. G jest planarne. G jest dwustronny. Nie dbam o żadne struktury lub ..., po prostu muszę policzyć wszystkie połączone podgrupy! Interesuje mnie również złożoność zliczania wszystkich połączonych podsgrafów z dokładnie …
Grupa Clifford operatorów kwantowej są generowane przez operacje kwantowej: Controlled-Z , Hadamard i Faza ( ).=|0⟩⟨0|+i|1⟩⟨1|=|0⟩⟨0|+i|1⟩⟨1|= |0\rangle\langle0| + i |1\rangle\langle1| Obwód złożony tylko z tych bram może być skutecznie symulowany na klasycznym komputerze. Jednak, jeśli dobrze rozumiem, nie wszystkie klasyczne algorytmy mogą być skutecznie wdrożone przy użyciu operacji grupowych Clifford, …
Pracując nad nieco niezwiązanym projektem dla Suresh, ostatnio natknąłem się na pracę wykonaną przez Page i Opper na temat systemów tworzonych przez użytkowników, a część ich pracy krótko omówiła problemy, których nie można zweryfikować w czasie wielomianowym. Nie udało mi się znaleźć wielu informacji o innych problemach, których nie można …
Niedawno przypomniano mi o problemie vs. jak wyjaśnił Stephen A. Cook z Clay Mathematics Institute.N PP.P.\mathsf{P}N P.N.P.\mathsf{NP} To wzbudziło moje zainteresowanie i chciałbym dowiedzieć się więcej na ten temat. Pierwszym krokiem byłoby lepsze zrozumienie problemu i ogólne zrozumienie tego obszaru. Czy możesz polecić jakieś książki lub inne zasoby, w których …
Zliczając argumenty, można pokazać, że istnieją wielomiany stopnia n w 1 zmiennej (tj. Coś w postaci które mają złożoność obwodu n. Można również pokazać, że wielomian taki jak wymaga co najmniej mnożenia (potrzebujesz tego tylko, aby uzyskać wystarczająco wysoki stopień). Czy są jakieś wyraźne przykłady wielomianów w 1 zmiennej o …
Zastanawiam się konkretnie, czy istnieje interesujący warunek dotyczący odsetka zadań spełniających formułę 3SAT, aby zagwarantować, że takie problemy są możliwe do rozwiązania. Załóżmy na przykład, że klasa problemów 3SAT z 2 n możliwych przypisań spełnia wzór logiczny; czy możemy skutecznie znaleźć satysfakcjonujące zadanie? Po co ϵ wynika problem w P?ϵ …
Biorąc pod uwagę termin t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y))z teorii typów Martina-Lofa, jaka jest wartość w(t(0)), gdzie wjest operator wydobywający świadka terminu typu egzystencjalnego?
Używamy plików cookie i innych technologii śledzenia w celu poprawy komfortu przeglądania naszej witryny, aby wyświetlać spersonalizowane treści i ukierunkowane reklamy, analizować ruch w naszej witrynie, i zrozumieć, skąd pochodzą nasi goście.
Kontynuując, wyrażasz zgodę na korzystanie z plików cookie i innych technologii śledzenia oraz potwierdzasz, że masz co najmniej 16 lat lub zgodę rodzica lub opiekuna.