Losowa funkcja monotoniczna


15

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 dowodach są wykonalne - ale wydaje się, że nie ma dobrego formalnego odpowiednika warunku wielkości. W szczególności nikt nie sformułował praktycznej definicji „losowej funkcji monotonicznej”.

Czy nie jest łatwo odróżnić wyjścia funkcji monotonicznej od losowego ciągu? Czy istnienie silnych dolnych granic nie mówi nam, że takich rzeczy nie ma?

Moje pytanie brzmi:

Co rozumieją przez wykonalną definicję „losowej funkcji monotonicznej” ?



nie do końca pewni, co mieli na myśli. istnieje tak naprawdę bardzo naturalny sposób definiowania losowych funkcji wycinania monotonicznego. także praca Rossmana na temat monotonicznej złożoności kliki k na losowych grafach wykorzystuje grafy erdos-renyi, które w rzeczywistości są również całkiem naturalne. pamiętaj, że papier z próbami naturalnymi ma już ponad 1,5 dekady.
vzn

Odpowiedzi:


12

Nie jestem pewien, ale myślę, że problem polega na tym, że nie mamy żadnych silnych założeń na temat pseudolosowych generatorów funkcji monotonicznych (przynajmniej takich, o których wiem). Idea dowodu w pracy Razborova-Rudicha jest następująca:

jeśli istnieje naturalna właściwość funkcji (tj. efektywnie rozstrzygalna właściwość, która utrzymuje wystarczająco duży podzbiór funkcji i implikuje, że funkcja wymaga dużych obwodów), można jej użyć do przerwania generatorów funkcji pseudolosowych (co psuje również generatory pseudolosowe i jeden funkcje -way).

Jeśli mielibyśmy powtórzyć twierdzenie w kategoriach funkcji monotonicznych i obwodów monotonicznych, chcielibyśmy powiedzieć

jeśli istnieje naturalna właściwość funkcji monotonicznych (tj. efektywnie rozstrzygalna właściwość, która utrzymuje wystarczająco duży podzbiór funkcji monotonicznych i implikuje, że funkcja wymaga dużych obwodów monotonicznych ), wówczas można jej użyć do przerwania generatorów funkcji pseudolosowych (co psuje również pseudolosowy generatory i funkcje jednokierunkowe),

ale teraz dowód z papieru przestaje działać, ponieważ nasz generator pseudolosowy generuje funkcje ogólne, niekoniecznie monotoniczne, i nie możemy użyć naszej własności naturalnej do jego złamania, ponieważ nawet stosunkowo duży podzbiór funkcji monotonicznych nie będzie duży w stosunku do funkcje ogólne, ponieważ sam zestaw funkcji monotonicznych nie jest duży w stosunku do zestawu wszystkich funkcji ( http://en.wikipedia.org/wiki/Dedekind_number ). Moglibyśmy zdefiniować jakiś pseudolosowy generator funkcji monotonicznej i użyć jego właściwości naturalnej do jego złamania, ale prawdopodobnie nie mielibyśmy równoważności między tym generatorem a funkcjami jednokierunkowymi, więc twierdzenie nie byłoby tak interesujące.

Być może tę trudność można naprawić (ale nie sądzę, że wynika to z dowodu zawartego w artykule w prosty sposób), a może problem z funkcjami monotonicznymi leży gdzie indziej. Naprawdę chciałbym, aby ktoś bardziej doświadczony ode mnie potwierdził moją odpowiedź lub pokazał, gdzie się mylę.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.