Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i...
To pytanie zostało przeniesione z Cross Validated, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 8 lat temu . Mam dość unikalny problem do rozwiązania i mam nadzieję, że ktoś tutaj da mi wgląd w to, jak najlepiej go...
Problem nie wszystkie równe SAT (NAE -SAT), biorąc pod uwagę zbiór klauzul nad zestawem zmiennych boolowskich, tak że każda klauzula zawiera co najwyżej literałów, pyta, czy istnieje przyporządkowanie zmiennych do takich wartości, że każda klauzula zawiera co najmniej jeden prawdziwy i co najmniej...
W obecnej formie to pytanie nie pasuje do naszego formatu pytań i odpowiedzi. Oczekujemy, że odpowiedzi poparte będą faktami, referencjami lub wiedzą fachową, ale to pytanie prawdopodobnie będzie wymagało debaty, argumentów, ankiet lub rozszerzonej dyskusji. Jeśli uważasz, że to...
Czy ktoś może zasugerować dobrą i najnowszą ankietę na temat liczenia problemów i / lub problemów, które są #P.
Zastanawiałem się, jakich narzędzi używają ludzie z tej dziedziny (teoretyczna informatyka) do tworzenia prezentacji. Ponieważ duża część informatyki to nie tylko pisanie artykułów, ale także wygłaszanie prezentacji, pomyślałem, że będzie to ważne miękkie pytanie. Jest to inspirowane poprzednim...
Zainspirowany rozległymi hierarchiami obecnymi w teorii złożoności, zastanawiałem się, czy takie hierarchie występują również w przypadku systemów typów. Jednak dwa przykłady, które do tej pory znalazłem, bardziej przypominają listy kontrolne (z funkcjami ortogonalnymi) niż hierarchie (z coraz...
Ostatnio otrzymuję odrzucenie moich artykułów z czasopism (tj. TALG) z tego powodu, że nie mam znaczącej różnicy między wersją czasopisma a wersją postępowania (tj. SODA). Głównym powodem, dla którego przesyłam do czasopisma, jest jego dokładny proces recenzji. Poza tym, limit 20 stron SODA to...
W praktyce, dla języka, który można ostatecznie skompilować / przekształcić w instrukcje na poziomie systemu, czy konieczne jest, aby była to gramatyka bezkontekstowa? np .: Czy wszystkie języki programowania / skryptów są wolne od kontekstu? Java oparta jest na CFG, ale czy w rzeczywistości...
Wiadomo, że cykl hamiltonowski (w skrócie szynka) jest zakończony NP, a cykl szynki Planar jest zakończony NP. Dowód na cykl szynkowy nie pochodzi z cyklu szynkowego. Czy jest fajny gadżet, który, biorąc pod uwagę wykres G, zastąpi wszystkie skrzyżowania jakimś płaskim gadżetem, dzięki czemu masz...
Rozważmy wypukłe ciało wyśrodkowane na początku i symetryczne (tj. Jeśli to ). Chcę znaleźć inne ciało wypukłe tak aby i następująca miara zostały zminimalizowane:x ∈ K - x ∈ K L K ⊆ L.KKKx∈Kx∈Kx\in K−x∈K−x∈K-x\in KLLLK⊆LK⊆LK\subseteq L xf(L)=E(xT⋅x−−−−−√)f(L)=E(xT⋅x)f(L)=\mathbb{E}(\sqrt{x^T...
Zainspirowany tym pytaniem , jakie są główne problemy i istniejące rozwiązania, które wymagają ulepszenia w (teoretycznej) dziedzinie systemów rozproszonych. Coś jak protokoły członkostwa, spójność
Staram się dowiedzieć, jak blisko i naprawdę są, gdy i jest stałą nie zależnie od n (tak ). Szacuję, że whp, ale nie byłem w stanie tego udowodnić.t w ( G )tw(sol)tw(G)mi[ t w ( G ) ]E[tw(sol)]E[tw(G)]G ∈ G ( n , p = c / n )sol∈sol(n,p=do/n)G \in G(n,p=c/n)c > 1do>1c>1mi[ t w ( G ) ] = Θ ( n...
W obliczeniach kwantowych często interesują nas przypadki, w których grupa specjalnych operatorów unitarnych, G, dla jakiegoś systemu d-wymiarowego daje dokładnie całą grupę SU (d), a nawet tylko przybliżenie zapewniane przez gęstą osłonę SU (d). Grupa skończonego rzędu, taka jak grupa Clifforda...
Powstrzymanie problemu twierdzi, że niemożliwe jest napisanie programu, który może określić, czy kolejne przystanków programowych dla wszystkich możliwych programów wejściowych . Mogę jednak z pewnością napisać program, który może obliczyć czas działania programu takiego jak: for(i=0; i<N;...
Wiemy, że maksymalny niezależny zestaw (MIS) jest trudny do przybliżenia przy współczynniku dla dowolnego ϵ > 0, chyba że P = NP. Jakie są specjalne klasy wykresów, dla których znane są lepsze algorytmy aproksymacyjne?n1−ϵn1−ϵn^{1-\epsilon}ϵ>0ϵ>0\epsilon > 0 Jakie są wykresy, dla których...
Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym...
Ostatnio widziałem kilka artykułów na temat arxiv, które odnoszą się do systemu sprawdzania zwanego sumą kwadratów. Czy ktoś może wyjaśnić, co to jest dowód sumy kwadratów i dlaczego takie dowody są ważne / interesujące? Jak są one powiązane z innymi algebraicznymi systemami dowodowymi? Czy są...
Biorąc pod uwagę zestaw SS.S osób, chciałbym im usiąść na sekwencji posiłków przy stolikach wielkości . (Oczywiście, jest wystarczająca ilość stolików, aby usiąść przy każdym posiłku.) Chciałbym tak ustawić, aby nikt nie dzielił stołu z tą samą osobą dwa razy. Typowe wartości to...
Opublikowałem to wcześniej na MSE, ale zasugerowano, że może być lepsze miejsce do zapytania. Uniwersalne twierdzenie o aproksymacji stwierdza, że „standardowa wielowarstwowa sieć przesyłowa z pojedynczą ukrytą warstwą, która zawiera skończoną liczbę ukrytych neuronów, jest uniwersalnym...