Dowód, że górne granice obwodu dla

18

W oficjalnym opisie problemu Clay dla P kontra NP stwierdzono, że wynikałoby z pokazania, że „każdy język w [klasa języków rozpoznawalnych w czasie wykładniczym z deterministyczną maszyną Turinga] może być obliczony przez rodzinę obwodów boolowskich , tak że co najmniej jedno , jest mniejsze niż maksymalna bramy potrzebny do obliczenia dowolnego logiczna funkcja $P \neq NP$ $E$ $<B_n>$ $n$ $B_n$ $f: \{0,1\}^n \longrightarrow \{0,1\}$ „Jednak jedynym odniesieniem jest to, że” to intrygująca obserwacja V. Kabanetsa. „Czy ktoś mógłby mi wskazać opublikowaną wersję tej implikacji z dowodem?

cc.complexity-theory circuit-complexity David
źródło

25

Nie sądzę, że artykuł w drugiej odpowiedzi zawiera odpowiedź na twoje pytanie. Rzeczywiście nie jestem pewien, czy opublikowano dowód, ponieważ wynik wynika z innych dobrze znanych wyników.

Dowód żądanego oświadczenia jest następujący:

zawiera funkcję maksymalnej możliwej złożoności obwodu na każdej długości wejściowej, po prostu definiując funkcję, która okazuje się (przy użyciu przemienności), że różni się od wszystkich funkcji o nie-maksymalnej złożoności obwodu. Jest to standard, a pomysł na dowód można znaleźć w źródłach takich jak Arora i podręcznik Baraka. $\Sigma_3 E$
Jeżeli następnie , przez napawanie i załamania wielomianu hierarchii czasu do . $P = NP$ $\Sigma_3 E = E$ $P$
Dlatego jeśli to w występuje język o maksymalnej złożoności obwodu. To jest przeciwieństwo tego, co chcesz udowodnić. $P = NP$ $E$

Ryan Williams
źródło

Fajnie, zgadłem, że jako pierwszy odpowiesz na to pytanie.

Mohammad Al-Turkistany

4

Odpowiedź znajduje się również w artykule Kabanets i Cai. W Twierdzeniu 10 dowodzą, że jeśli

jest w

, to

zawiera rodzinę funkcji boolowskich o maksymalnej złożoności obwodu. Jeśli

, to

i

, więc według twierdzenia

rzeczywiście zawiera język o maksymalnej złożoności.

M C S P

$MCSP$

P

$P$

E^{N P}

$E^{NP}$

P = N P

$P=NP$

M C S P \in P

$MCSP\in P$

E^{N P} = E

$E^{NP}=E$

E

$E$

Andras Farago,

1

dobra uwaga, Andras! Jeden z kwantyfikatorów w części

może być postrzegany jako rozwiązanie MCSP.

Σ_{3} E

$\Sigma_3 E$

Ryan Williams

6

googling dookoła znalazł mi ten artykuł, który został opublikowany z poniższym odniesieniem.

Problem minimalizacji obwodu

Valentine Kabanets i Jin-Yi Cai

Badamy złożoność problemu minimalizacji obwodu: biorąc pod uwagę tabelę prawdy funkcji boolowskiej f i parametru s, decydujemy, czy f może być zrealizowane przez obwód boolowski wielkości co najwyżej s. Argumentujemy, dlaczego jest mało prawdopodobne, aby problem ten występował w P (lub nawet w P / poli), podając szereg zaskakujących konsekwencji takiego założenia. Twierdzimy również, że udowodnienie, że ten problem jest NP-zupełny (jeśli to rzeczywiście prawda), oznaczałoby udowodnienie silnych dolnych granic obwodu dla klasy E, co wydaje się wykraczać poza obecnie znane techniki.

Wydawało się, że zostało to opublikowane poniżej.

rozszerzony streszczenie w materiałach trzydziestego drugiego dorocznego sympozjum ACM na temat teorii obliczeń (STOC'00), strony 73-79, 2000. raport techniczny, w Electronic Colloquium na temat złożoności obliczeniowej TR99-045, 1999. http: // www. cs.sfu.ca/~kabanets/Research/circuit.html
rozszerzony streszczenie w materiałach trzydziestego drugiego dorocznego sympozjum ACM na temat teorii obliczeń (STOC'00), strony 73-79, 2000. http://eccc.hpi-web.de/report/1999/045/

Joshua Herman
źródło

Zauważ, że ta odpowiedź nie odpowiada na powyższe pytanie, ale zawiera odniesienie, z którego pochodzi to pytanie.

Joshua Herman

Dowód, że górne granice obwodu dla

Odpowiedzi: