Reductions in PPP
| Autor: | Kamal Jain, Frank Ban, Christos H. Papadimitriou, Aviad Rubinstein, Christos-Alexandros Psomas |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Class (set theory) Conjecture business.industry Pigeonhole principle Cryptography Dirichlet distribution Computer Science Applications Theoretical Computer Science Computer Science::Robotics symbols.namesake Signal Processing Minkowski space symbols Complexity class Physics::Chemical Physics business Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 145:48-52 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2018.12.009 |
| Popis: | We show several reductions between problems in the complexity class PPP related to the pigeonhole principle, and harboring several intriguing problems relevant to Cryptography. We define a problem related to Minkowski's theorem and another related to Dirichlet's theorem, and we show them to belong to this class. We also show that Minkowski is very expressive, in the sense that all other non-generic problems in PPP considered here can be reduced to it. We conjecture that Minkowski is PPP-complete. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect