Home > Search Results: keywords:"Booleovská formule|formální míra složitosti|dolní odhady"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.00 seconds. 
Lower Bounds on Boolean Formula Size
 Fojtík, Vít ; Hrubeš, Pavel (advisor) ; Savický, Petr (referee)
The aim of this thesis is to study methods of constructing lower bounds on Boolean formula size. We focus mainly on formal complexity measures, gener- alizing the well-known Krapchenko measure to a class of graph measures, which we thereafter study. We also review one of the other main approaches, using ran- dom restrictions of Boolean functions. This approach has yielded the currently largest lower bounds. Finally, we mention a program for finding super-polynomial bounds based on the KRW conjecture. 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English