W 1995 r. Russell Impagliazzo zaproponował pięć światów złożoności: 1- Algorytmika: ze wszystkimi niesamowitymi konsekwencjami.P.= NP.P.=N.P.P=NP 2- Heuristica: problemy kompletne są trudne w najgorszym przypadku ( ), ale można je skutecznie rozwiązać w przeciętnym przypadku.N.P.N.P.NPP.≠...
Kilka lat temu była praca Joela Friedmana związana z dolnymi granicami obwodu z kohomologią Grothendiecka (patrz dokumenty: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Czy ten sposób myślenia przyniósł jakieś nowe spojrzenie na złożoność logiczną, czy pozostaje raczej...
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta jest zawarta w...
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników...
Niech faff będzie funkcją boolowską i pomyślmy o f jako funkcji od {−1,1}n{−1,1}n\{-1,1\}^n do {−1,1}{−1,1}\{ -1,1 \} . W tym języku ekspansja Fouriera f jest po prostu ekspansją f pod względem kwadratowych wolnych jednomianów. (Te 2n2n2^n monomialów stanowią podstawę dla przestrzeni funkcji...
Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą.XXXXXXX Pod jakimi warunkami wiadomo, że „X to NP-zupełny” że „X jest kompletny?⟹⟹\implies Oczywiście istnienie skąpej redukcji jest jednym z takich warunków, ale jest to oczywiste i jedyny taki warunek, o którym wiem....
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...
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 ,...
Napraw liczbę całkowitą i alfabet Σ = { 0 , 1 } . Zdefiniuj D F A ( n ) jako zbiór wszystkich automatów skończonych w stanach n ze stanem początkowym 1. Rozważamy wszystkie DFA (nie tylko połączone, minimalne lub nie-zdegenerowane); w ten sposób | D F A ( n ) | = n 2 n 2 n...
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
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 złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że 3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy...
Jaka jest złożoność decyzji, czy obwód z n bitami wejściowymi i n bitami wyjściowymi oblicza permutację { 0 , 1 } n ? innymi słowy, czy każdy ciąg bitów w { 0 , 1 } n jest wyjściem obwodu dla niektórych danych wejściowych? Wygląda na problem, który został zbadany, ale nie mogę znaleźć żadnych...
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...
Jakie byłyby konsekwencje #P = FP? Interesują mnie zarówno praktyczne, jak i teoretyczne konsekwencje. Z praktycznego punktu widzenia szczególnie interesują mnie konsekwencje dla sztucznej inteligencji. Wskaźniki do dokumentów lub książek są mile widziane. Nie mów, że #P = FP oznacza P = NP,...
Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam...
Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S ⊆ V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje...
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są...
Pytanie: Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)Ω(n2)\Omega(n^2) Tło: Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły...
Przepraszamy za zadawanie pytań, które z pewnością muszą znaleźć się w wielu standardowych źródłach. Ciekawi mnie dokładnie pytanie zawarte w tytule, w szczególności myślę o obwodach boolowskich, bez ograniczeń głębokości. W cudzysłowie wstawiam „najmniejszy”, aby umożliwić istnienie wielu różnych...