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 =
Myślę, że twierdzenie o hierarchii wielkości dla złożoności obwodów może być dużym przełomem w tej dziedzinie. Czy to ciekawe podejście do separacji klasowej? Motywem tego pytania jest to, że musimy powiedzieć istnieje pewna funkcja, której nie można obliczyć na podstawie obwodów wielkości...
Dowody naturalne stanowią barierę dla udowodnienia niższych granic złożoności obwodu funkcji boolowskich. Nie bezpośrednio wynika, takiej bariery dla udowodnienia niższe granice na obwód złożoności. Czy jest jakiś postęp w identyfikowaniu takich barier? Czy istnieją inne bariery w ustawieniu...
W artykule „ Naturalne dowody” Razborova-Rudicha , strona 6, w części, w której dyskutują, że istnieją „silne dowody dolnej granicy na modele obwodów monotonicznych ” i to, jak pasują do zdjęcia, są następujące zdania: Tutaj nie chodzi o konstruktywność - wszystkie właściwości użyte w tych...