tło
Formuła „read-once” na zbiorze bramek (zwana również podstawą) to formuła, w której każda zmienna wejściowa pojawia się jeden raz. Formuły do odczytu raz są powszechnie badane na podstawie De Morgana (która ma 2-bitowe bramki AND i OR oraz 1-bitową bramkę NOT) i pełnej bazy binarnej (która ma wszystkie 2-bitowe bramki).
Na przykład, AND 2 bitów można zapisać jako formułę jednokrotnego odczytu na dowolnej podstawie, ale parzystości 2 bitów nie można zapisać jako formuły jednorazowej na podstawie De Morgana.
Zestaw wszystkich funkcji, które można zapisać jako formułę „raz do odczytu” na podstawie De Morgana, ma charakter kombinatoryczny. Patrz na przykład kombinatoryjna charakterystyka formuł „raz do odczytu” autorstwa M. Karchmera, N. Liniala, I. Newmana, M. Saksa, A. Wigdersona.
Pytanie
Czy istnieje alternatywna charakterystyka zestawu funkcji, którą można obliczyć za pomocą formuły „raz do odczytu” w pełnej bazie binarnej?
Łatwiejsze pytanie (dodane w v2)
Chociaż nadal jestem zainteresowany odpowiedzią na pierwotne pytanie, ponieważ nie otrzymałem żadnych odpowiedzi, pomyślałem, że zadam łatwiejsze pytanie: Jakie są techniki o niższych granicach, które działają dla formuł w oparciu o pełną bazę binarną? (Inne niż te wymienione poniżej.)
Zauważ, że teraz próbuję obniżyć granicę rozmiaru formuły (= liczba liści). W przypadku formuł „raz do odczytu” mamy formułę rozmiar = liczba danych wejściowych. Jeśli więc możesz udowodnić, że funkcja potrzebuje formuły wielkości ściśle większej niż n, oznacza to również, że nie może być reprezentowana jako formuła do odczytu.
Znam następujące techniki (wraz z odniesieniem do każdej techniki z Boolean Function Complexity: Advances and Frontiers autorstwa Stasys Jukna ):
źródło
Odpowiedzi:
istnieje również metoda zwana dolną granicą Krapczenki „która może być nieco większa niż metoda Nechiporuksa”. patrz John E Savage, Modele obliczeń, rozdział 9.4.2. (który omówiono zaraz po metodzie Nechiporuk w sekcji 9.4.1)
źródło