|
|
NP vyhledávací problémy a redukce mezi nimi
Ševčíková, Renáta ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
NP search problems and reductions among them Renáta Ševčíková In the thesis we study the class of Total NP search problems. More attention is devoted to study the subclasses of Total NP search problems and reductions among them. We combine some known methods: the search trees and their relation to re- ductions, the Nullstellensatz refutation and the degree lower bound based on design to show that two classes of relativized NP search problems based on Mod-p counting principle and Mod-q counting principle, where p and q are different primes, are not reducible to each other. This thesis is finished by a new separation result for p = 2 and q = 3.
|
|
|
DPLL algorithm and propositional proofs
Hrnčiar, Maroš ; Krajíček, Jan (advisor) ; Koucký, Michal (referee)
Proof complexity is an interesting mathematical part connecting logic and complexity theory. It investigates which proof systems are needed for effective theorem proving. The aim of this paper is to present a relation between propositional proof systems and SAT algorithms. We will see that a run of an algorithm on the unrealizable formula can be seen as a propositional proof of its unsatisfiability, so the algorithm practically defines whole proof system. The thesis is mainly recommended for readers interested in proof complexity, but it can also independently illustrate a resolution principle and perhaps show some less common view of SAT assuming reader's basic knowledge of propositional logic, graph theory and complexity.
|
|
| |
|
|
Těžké tautologie
Pich, Ján ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
We investigate the unprovability of NP$\not\subseteq$P/poly in various fragments of arithmetic. The unprovability is usually obtained by showing hardness of propositional formulas encoding superpolynomial circuit lower bounds. Firstly, we discuss few relevant techniques and known theorems. Namely, natural proofs, feasible interpolation, KPT theorem, iterability, gadget generators etc. Then we prove some original results. We show the unprovability of superpolynomial circuit lower bounds for systems admitting certain forms of feasible interpolation (modulo a hardness assumption) and for systems roughly described as tree-like Frege systems working with formulas using only a small fraction of variables of the statement that is supposed to be proved. These results are obtained by proving the hardness of the Nisan-Wigderson generators in corresponding proof systems.
|
|
| |
|
|
Deniable encryption
Šebek, Marcel ; Tůma, Jiří (advisor) ; Krajíček, Jan (referee)
In the thesis we study deniable encryption, as proposed by Canetti et al. (CRYPTO 1997). Standard encryption schemes guarantee good security level unless the adversary is able to force the sender and/or receiver to reveal her secret knowledge. Assuming that the adversary knows true ciphertext, the se- cret inputs usually commits the sender/receiver to the true plaintext. On the contrary, deniable scheme is equipped with algorithms that provide alternative secrets which makes the adversary believe that different plaintext was encrypted. We recall the most important results in the area, in particular, the schemes of Canetti et al. (CRYPTO 1997), the scheme of Klonowski et al. (SOFSEM 2008) based on ElGamal encryption, schemes of O'Neill et al. (CRYPTO 2011), and schemes and impossibility result of Bendlin et al. (ASIACRYPT 2011). In ad- dition to presenting known results in an unified environment, we deeply investi- gate simulatable-encryption based schemes. In particular, we construct a scheme that is bideniable, and both of its induced schemes are receiver-deniable (in the flexible/multi-distributional setting). We also disprove part of the results of Bendlin et al. (ASIACRYPT 2011) by showing that their construction of fully bideniable scheme is wrong. This result is verified using computer simulation....
|
|
|
Spectrum problem
Poláková, Kristýna ; Krajíček, Jan (advisor) ; Jeřábek, Emil (referee)
In the present work we study the spectrum problem that was introduced by H. Scholz in 1952. We define the basic concepts associated with this problem. We follow its further development, especially context with sets from complexity class NE. We defined a generalized spectra. We introduce examples of sets of natural numbers, which are spectra.
|
|
| |
|
|
Communication complexity
Wagner, Vojtěch ; Krajíček, Jan (advisor) ; Koucký, Michal (referee)
Title: Communication Complexity Author: Vojtěch Wagner Department: Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Abstract: This work deals with communication complexity, which considers mo- del of two (or more) parties, each holding its own binary input (let's say x and y). Each of players has information only about his own input. Their common goal is to compute value of some function f(x, y) of these inputs. Communicati- on complexity measures amount of information communicated between players in order to compute f(x, y). This work especially concerns two main models - deterministic, in which all decision made by players is deterministic and they compute the right value in all cases and probabilistic model which allows ran- domized fashion and the goal of the players is to compute the right value with high enough probability. We present some basic concepts and methods to lower bound communication complexity of functions, all ilustrated on some examples of basic functions. In the end we present some complex and practically relevant examples, on which presented methods are demonstrated. Keywords: communication complexity, deterministic communication model, ran- domized model, lower bounds on communication complexity. 1
|
|
| |
guest ::
RSS feed.