Lower Bounds on Boolean Formula Size

Fojtík, Vít

Dolní odhady velikosti Booleovských formulí

dc.contributor.advisor	Hrubeš, Pavel
dc.creator	Fojtík, Vít
dc.date.accessioned	2019-07-10T14:55:35Z
dc.date.available	2019-07-10T14:55:35Z
dc.date.issued	2019
dc.identifier.uri	http://hdl.handle.net/20.500.11956/107745
dc.description.abstract	Cı́lem této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW doměnce. 1	cs_CZ
dc.description.abstract	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	en_US
dc.language	English	cs_CZ
dc.language.iso	en_US
dc.publisher	Univerzita Karlova, Filozofická fakulta	cs_CZ
dc.subject	Boolean formula\|Formal complexity measure\|Lower bounds	en_US
dc.subject	Booleovská formule\|formální míra složitosti\|dolní odhady	cs_CZ
dc.title	Lower Bounds on Boolean Formula Size	en_US
dc.type	bakalářská práce	cs_CZ
dcterms.created	2019
dcterms.dateAccepted	2019-06-19
dc.description.department	Department of Logic	en_US
dc.description.department	Katedra logiky	cs_CZ
dc.description.faculty	Faculty of Arts	en_US
dc.description.faculty	Filozofická fakulta	cs_CZ
dc.identifier.repId	205426
dc.title.translated	Dolní odhady velikosti Booleovských formulí	cs_CZ
dc.contributor.referee	Savický, Petr
thesis.degree.name	Bc.
thesis.degree.level	bakalářské	cs_CZ
thesis.degree.discipline	Logic	en_US
thesis.degree.discipline	Logika	cs_CZ
thesis.degree.program	Logic	en_US
thesis.degree.program	Logika	cs_CZ
uk.thesis.type	bakalářská práce	cs_CZ
uk.taxonomy.organization-cs	Filozofická fakulta::Katedra logiky	cs_CZ
uk.taxonomy.organization-en	Faculty of Arts::Department of Logic	en_US
uk.faculty-name.cs	Filozofická fakulta	cs_CZ
uk.faculty-name.en	Faculty of Arts	en_US
uk.faculty-abbr.cs	FF	cs_CZ
uk.degree-discipline.cs	Logika	cs_CZ
uk.degree-discipline.en	Logic	en_US
uk.degree-program.cs	Logika	cs_CZ
uk.degree-program.en	Logic	en_US
thesis.grade.cs	Výborně	cs_CZ
thesis.grade.en	Excellent	en_US
uk.abstract.cs	Cı́lem této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW doměnce. 1	cs_CZ
uk.abstract.en	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	en_US
uk.file-availability	V
uk.publication.place	Praha	cs_CZ
uk.grantor	Univerzita Karlova, Filozofická fakulta, Katedra logiky	cs_CZ
thesis.grade.code	1