Uwaga: chodzi o standardową łamigłówkę sudoku 9x9. Rozwiązanie musi obsługiwać tylko rozwiązane, legalne zagadki . Dlatego rozwiązanie nie musi obsługiwać pustych komórek i może polegać na właściwościach rozwiązanej łamigłówki sudoku. Zastanawiałem się nad tym, ale nie mogłem wymyślić odpowiedzi,...
Niech jest stopień d wielomian n zmienne przez F 2 , w którym d jest stała (przykładowo 2 lub 3). Chciałbym znaleźć najmniejszą formułę dla f , gdzie „formuła” i „rozmiar formuły” są zdefiniowane w oczywisty sposób (np. Najmniejsza formuła dla wielomianu x 1 x 2 + x 1 x 3 to x 1 ( x 2 + x 3 )...
Złożoność prefiksu Kołmogorowa (tj. to rozmiar minimalnego programu do rozgraniczania, który generuje x ), ma kilka fajnych cech:K(x)K(x)K(x)xxx Odpowiada to intuicji nadawania łańcuchom z wzorami lub struktury mniejszej złożoności niż łańcuchy bez. To pozwala nam na zdefiniowanie warunkowego...
Czy są jakieś przykłady zabawek, które zapewniają „niezbędny” wgląd w trzy znane bariery dla problemu - relatywizacja, dowody naturalne i algebryzacja?P=NPP=NPP =
Załóżmy, że mam poset „S” i monotoniczny predykat „P” na S. Chcę znaleźć jeden lub wszystkie maksymalne elementy S spełniające P. EDIT : Jestem zainteresowany minimalizując liczbę ocen P . Jakie algorytmy istnieją dla tego problemu i jakich właściwości i dodatkowych operacji wymagają na S? Co z...
Zastanawiałem się, czy istnieje `` lepszy '' (wyjaśnię, w jakim sensie) algorytm rozpoczynający się od DFA i konstruujący wyrażenie regularne r takie, że L ( A ) = L ( r ) , niż ten w książka Hopcroft i Ullman (1979). Tam, zbiory R k i j są używane do reprezentowania komplety strun, które odbywają...
Prezentowałem wykład na temat sortowania naleśników i wspomniałem, że: Sortowanie według zamian jest trudne „podpisany” sortując odwrócenia jest w P . Co skłoniło mnie do myślenia. W pewnym sensie sortowanie „sygnowane” jest „ukierunkowane” - możesz postrzegać znak jako kierunek (i rzeczywiście...
Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL....
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe)...
W swojej książce Boolean Function Complexity Stasys Jukna wspomina (strona 564), że Kołmogorow wierzył, że każdy język w P ma obwody o wielkości liniowej. Nie ma wzmianki o referencjach i nie mogłem znaleźć niczego online. Czy ktoś wie o tym
Istnieje kilka algorytmów, które decydują w czasie wielomianowym, czy wykres może być narysowany w płaszczyźnie, czy nie, nawet wiele z czasem liniowym. Jednak nie mogłem znaleźć bardzo prostego algorytmu, który można łatwo i szybko wyjaśnić na zajęciach i pokazać, że PLANARNOŚĆ znajduje się w P....
Ostatnio studiuję Haskell i języki programowania. Czy ktoś mógłby polecić jakieś książki na temat teorii
Pytanie dotyczące teorii „ Co to jest NP ograniczony do świadków wielkości liniowej? ” Dotyczy klasy NP ograniczonej do świadków wielkości liniowej , aleO ( n )O(n)O(n) Czy istnieją naturalne problemy NP-zupełne, w których (tak) przypadki wielkości wymagają świadków o rozmiarze większym niż n...
W tym artykule na Wikipedii o kompletności Turinga stwierdza się, że: Rachunek lambda bez typu jest zakończony przez Turinga, ale wiele typowych rachunków lambda, w tym System F, nie jest. Wartość typowanych systemów polega na ich zdolności do reprezentowania najbardziej typowych programów...
Dlaczego „sortowanie topologiczne” nazywa się „topologicznym”? Czy tylko dlatego, że określa kolejność bez zmiany wierzchołków lub krawędzi - jak pączek i filiżanka kawy są topologicznie równoważne? Dlaczego nie nazywa się to „sortowaniem zależności” lub czymś innym? Dlaczego „topologiczny”?...
Naprawmy kodowanie maszyn Turinga bez prefiksów i uniwersalną maszynę Turinga UUU która na wejściu (T,x)(T,x)(T,x) (zakodowana jako kod bez prefiksu TTT a następnie xxx ) wyprowadza dowolne TTT na wejściu xxx (ewentualnie oba działają wiecznie). Zdefiniuj złożoność Kołmogorowa dla xxx ,...
Wiemy, że (patrz np. Twierdzenia 1 i 3 z [1]), z grubsza mówiąc, w odpowiednich warunkach, funkcje, które mogą być skutecznie obliczone przez maszynę Turinga w czasie wielomianowym („wydajnie obliczalne”), mogą być wyrażone przez wielomianowe sieci neuronowe z rozsądnymi rozmiarami, a zatem można...
Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w...
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania...
W modelu czarnej skrzynki problem określania wydajności maszyny BPP na wejściu x jest przybliżonym problemem zliczania określania E r M ( x , r ) z błędem addytywnym 1/3 (powiedzmy) .M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Czy istnieje podobny problem dla BQP? Ten komentarz Kena Regana...