Jaka jest „najmniejsza” klasa złożoności, dla której

Wierzę, że odpowiedzi na to pytanie dają takie klasy, że dla wszystkich wielomianów $p$ ,
w klasie występuje problem, który nie ma obwodów wielkości $p(n)$ .
Pytam jednak o rozmiar obwodu $\omega \hspace{.02 in}(n)$ .

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ jest super-liniowy, ale nie $\omega \hspace{.02 in}(n)$ .
Chociaż takie parzyste i nieparzyste zachowanie można by obsłużyć przez wypełnienie, zamiast
tego można mieć wyjątkowo długie pasma wartości wielomianowych między niskimi wartościami).

circuit-complexity lower-bounds

— Społeczność
źródło

Myślę, że superliniowe dolne granice oznaczają, że istnieje ograniczenie dolne

ω (n)

$\omega(n)$ .

— Kaveh

Nie sądzę, byśmy nazywali to funkcją superliniową. O ile mi wiadomo, co ludzie rozumieją przez superslinear

ω (n)

$\omega(n)$ taki sam sposób, jak podliniowy

o (n)

$o(n)$ . Czy masz jakieś odniesienia do stosowania superslinearnego w twoim rozumieniu? Sekwencja jest nieskończenie często superliniowa, ale nie jest superliniowa.

— Kaveh

Uważam, że standardowym zastosowaniem jest to, że „obwód obwodu nieliniowego” oznacza, że nie ma obwodów wielkości

O (n)

$O(n)$ , czyli nieskończenie często. Dolne granice „Prawie wszędzie” są znacznie rzadsze i trudniejsze do osiągnięcia.

— Joshua Grochow

Zobacz post na blogu Fortnow na pytanie, jaka jest właściwa definicja dużej notacji omega.

— Robin Kothari,

@Kaveh: Przepraszam, powinienem był być bardziej szczegółowy. Miałem na myśli stwierdzenie, że „problem X nie ma obwodów o rozmiarze liniowym” jest ogólnie równoważne ze stwierdzeniem, że „problem X ma dolną granicę obwodu super-liniowego ” i uważam, że oba te znaczenia (i powinny oznaczać) to, co powiedziałem w moich poprzednich komentarzach. Wyrażenie „problem X ma obwody o rozmiarach superliniowych” wydaje mi się dziwne, ponieważ „posiadanie takich i takich obwodów” jest górną granicą, ale „superliniowe” to dolna granica ...

— Joshua Grochow

Odpowiedzi:

$S^p_2$ i $PP$ oboje wiadomo, że nie mają $n^k$ -obwody dla dowolnego ustalonego k i nie ma między nimi znanego zabezpieczenia. Szczegóły w moim poście na blogu .

Aktualizacja: jak zauważa Rickey Demer, wyniki te niekoniecznie dają język z dolną granicą dla wszystkich $n$ w $S_2^p$ . Myślę że $\Delta^p_3$ jest prawdopodobnie najbardziej znanym. Od $PP$ ma kompletne zestawy, które mogą być w stanie uzyskać wszystko $n$ związany, ale nie mam pełnego dowodu.

— Lance Fortnow
źródło

Jak przejść od "nie ma n

^{k}

$^k$ -size obwodów ”do

ω (n)

$\omega(n)$ Rozmiar obwodu dolna granica?

$\hspace{.84 in}$ Zobacz u góry tej strony sekwencję, która nie ma wielomianowej górnej granicy, ale jej nie ma

ω (n)

$\omega(n)$ .)

$\hspace{.58 in}$

@ EmilJeřábek: Jak to uzyskać dla wszystkich wystarczająco dużych

n

$n$ zamiast nieskończenie wielu

n

$n$ ?

$\hspace{.08 in}$ (To byłoby potrzebne, aby uzyskać „rozmiar obwodu to

ω (n)

$\omega(n)$ Rozmiar obwodu „zamiast” nie jest

O (n)

$O(n)$ .)

$\hspace{1.12 in}$

@ EmilJeřábek: Zobacz moją odpowiedź na meta.stackexchange.com/a/293100/232555 .

Masz rację, koncentrowałem się na pierwszej części dowodu, którego brakuje na blogu, i nie zdawałem sobie sprawy, że istnieje duży problem z rozróżnieniem sprawy. W każdym razie istnieje język

Δ_{3}^{P}

$\Delta^P_3$ który potrzebuje obwodów wielkości

\geq n^{k}

$\ge n^k$ dla wszystkich wystarczająco dużych

n

$n$ .

— Emil Jeřábek

Może uzyskać prawie wszędzie niższą granicę

P^{P P [n^{2}]}

$P^{PP[n^2]}$ . Dla każdego

n

$n$ , pozwolić

S

$S$ być zbiorem wszystkich obwodów wielkości

n \log n

$n\log n$ . Dla

i = 1, \dots, n^{2}

$i=1,\ldots,n^2$ , zadzwoń raz do wyroczni, aby ustalić, w co wchodzi większość obwodów

S

$S$ odpowiedz na

i

$i$ th wejście długości

n

$n$ i wyrzucić

S

$S$ wszystkie obwody, które dadzą tę odpowiedź (można to zakodować jako ograniczenie czasu policy w następnym wywołaniu Oracle). Nasza trudna funkcja wyświetli przeciwną wartość na

i

$i$ th wejście długości

n

$n$ .. Koniec dla. Teraz, biorąc pod uwagę ae-lb

P^{P P [n^{2}]}

$P^{PP[n^2]}$ możemy to podnieść

P P

$PP$ ?

— Ryan Williams,

Niech dMCSP będzie decydującą wersją problemu minimalnego rozmiaru obwodu
i niech „[1]” wskazuje „ tylko 1 zapytanie ”.
Odpowiedź na moje pytanie wydaje się być $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ , Który w rzeczywistości
jest taki, że dla każdej dodatniej liczby całkowitej k ma wartość $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$ Dolna granica:

Postępuj zgodnie z końcowym akapitem strony 7 tego artykułu wraz z akapitami tego akapitu $k$ będąc o jeden więcej niż ten argument $k$ i dodatkowo „zauważ, że zadaniem„ co_dMCSP ”jest ustalenie, czy
dana tabela prawd długości $\ell$ jest trudne”, w tym samym sensie, jak stosuje się w tym strona-7 ust.

W DNF obwody dowolnie długość- $\ell$ tabela prawdy ma co najwyżej rozmiar $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$ ,
więc dMCSP jest włączony $\mathbf{NP}$ . Dlatego $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$ .

Nie znam żadnego dowodu, że którykolwiek z nich $\subseteq$ s są równościami, a niniejszy dokument stwarza znaczne przeszkody dla możliwości istnienia dMCSP $\mathbf{NP}$ - twarde przy losowych redukcjach Turinga.
Równości wynikałyby z bycia dMCSP $\mathbf{NP}$ - twarde przy silnych niedeterministycznych ( strona 6 ) redukcjach jednego zapytania, które przyjmują ciąg porady wielkości wielomianowej, który jest obliczalny
przez $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ , Ale w szczególności nie jestem świadomy żadnego dowodu takiej twardości.