Reductions in PPP

•We introduce two new problems, Minkowski and Dirichlet.•We show that these two problems belong in the complexity class PPP.•We show that Equal Sums and Dirichlet are reducible to Minkowski. We show several reductions between problems in the complexity class PPP related to the pigeonhole principle,...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2019-05, Vol.145, p.48-52
Main Authors: Ban, Frank, Jain, Kamal, Papadimitriou, Christos H., Psomas, Christos-Alexandros, Rubinstein, Aviad
Format: Article
Language:English
Subjects:
Combinatorial problems
Computational complexity
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We introduce two new problems, Minkowski and Dirichlet.•We show that these two problems belong in the complexity class PPP.•We show that Equal Sums and Dirichlet are reducible to Minkowski. 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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2018.12.009