De Morgan Formula Size Catalogs for Small Boolean Functions
Fuente:
Zenodo
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Recurso digital |
| Publicado: |
Zenodo
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866901260387483648 |
|---|---|
| author | Alexander Towell |
| author_facet | Alexander Towell |
| contents | We compute the exact De Morgan formula size L(f) for all Boolean functions on n=3 (256 functions, max L=10) and n=4 (65,536 functions, max L=16) variables by bottom-up enumeration. All 114 hardest n=4 functions (L=16) are simultaneously maximal across sensitivity, block sensitivity, decision tree depth, and real degree. Partial n=5 results include L(THR(5,2))=12. |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19211132 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | De Morgan Formula Size Catalogs for Small Boolean Functions Alexander Towell formula complexity circuit complexity Boolean functions De Morgan formulas We compute the exact De Morgan formula size L(f) for all Boolean functions on n=3 (256 functions, max L=10) and n=4 (65,536 functions, max L=16) variables by bottom-up enumeration. All 114 hardest n=4 functions (L=16) are simultaneously maximal across sensitivity, block sensitivity, decision tree depth, and real degree. Partial n=5 results include L(THR(5,2))=12. |
| title | De Morgan Formula Size Catalogs for Small Boolean Functions |
| topic | formula complexity circuit complexity Boolean functions De Morgan formulas |
| url | https://doi.org/10.5281/zenodo.19211132 |