Enviar artigo por via de e-mail On a Relation Between the Depth and Complexity of Monotone Boolean Formulas
- Autores: Sergeev I.S.1
-
Afiliações:
- Scientific and Research Institute Kvant
- Edição: Volume 13, Nº 4 (2019)
- Páginas: 746-752
- Seção: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213294
- DOI: https://doi.org/10.1134/S1990478919040161
- ID: 213294
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
We present a sequence of monotone Boolean functions whose depth over the basis {∧, ∨} is c > 1.06 times greater than the logarithm of the formula complexity.
Palavras-chave
Sobre autores
I. Sergeev
Scientific and Research Institute Kvant
Autor responsável pela correspondência
Email: isserg@gmail.com
Rússia, Chetvyortyi Likhachyovskii per. 15, Moscow, 125438
Arquivos suplementares
