On the average-case complexity of underdetermined functions

DOI10.1515/DMA-2018-0019zbMath1393.68070OpenAlexW2888387164MaRDI QIDQ1669577

Aleksandr V. Chashkin

Publication date: 3 September 2018

Published in: Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/dma-2018-0019

zbMATH Keywords

Boolean functionaverage-case complexityBoolean circuitstraight-line programunderdetermined function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Cites Work

• On the complexity of realization of partial Boolean functions by circuits of functional elements
• On the complexity of Boolean matrices, graphs, and the Boolean functions corresponding to them
• Average time of computing Boolean operators
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the average-case complexity of underdetermined functions