Home > Search Results: keywords:"NP vyhľadávanie"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
Vyhledávací problémy a hledání kolizí pro hašovací funkce
 Čarnoký, Samuel ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Title: Search problems and search for collisions in hash functions Author: Samuel Čarnoký Department: The Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Supervisor's e-mail address: krajicek@karlin.mff.cuni.cz Abstract: Central points of this work are NP search problems and the existence of reductions amog them in the relativised world. Absolute separation would separate N from NP. In particular, we talk about the problem of finding collisions in hash functions that must exist due to the famous pigeonhole principle. We present a brief introduction into the topic, we define various NP search problems and recall reductions and separations. Reduction of weak version of PHP to a problem of finding a homogeneous subgraph is described and our own results are presented in the form of reduction of another variant of PHP to a problem related to finding paths in a graph. We talk about reducing the task of finding collisions in multiple functions into finding a collision in one function. Keywords: NP search, reductions, pigeonhole principle, oracles
Detailed record
Vyhledávací problémy a hledání kolizí pro hašovací funkce
 Čarnoký, Samuel ; Krajíček, Jan (advisor) ; Pudlák, Pavel (referee)
Title: Search problems and search for collisions in hash functions Author: Samuel Čarnoký Department: The Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Supervisor's e-mail address: krajicek@karlin.mff.cuni.cz Abstract: Central points of this work are NP search problems and the existence of reductions amog them in the relativised world. Absolute separation would separate N from NP. In particular, we talk about the problem of finding collisions in hash functions that must exist due to the famous pigeonhole principle. We present a brief introduction into the topic, we define various NP search problems and recall reductions and separations. Reduction of weak version of PHP to a problem of finding a homogeneous subgraph is described and our own results are presented in the form of reduction of another variant of PHP to a problem related to finding paths in a graph. We talk about reducing the task of finding collisions in multiple functions into finding a collision in one function. Keywords: NP search, reductions, pigeonhole principle, oracles
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