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 této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW domě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 této práce je studovat metody konstrukce dolnı́ch odhadů velikosti Booleovských formulı́. Soustředı́me se zde předevšı́m na formálnı́ mı́ry složitosti, přičemž zobecnı́me známou Krapchenkovu mı́ru na třı́du grafových měr, které následně studujeme. Zabýváme se také dalšı́m z hlavnı́ch přı́stupů, využı́vajı́cı́ náhodné restrikce Booleovských funkcı́. Na závěr zmı́nı́me program pro nalezenı́ super-polynomiálnı́ch odhadů založený na KRW domě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 | |