Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
PPP (complexity)
open-in-new
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> PPP (polynomial pigeonhole principle) is a subclass of <a href="/facts/TFNP/JwCmUwSV">TFNP</a>. It is the class of search problems that can be shown to be total by an application of the <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>. <a href="/facts/Christos_Papadimitriou/rXflR4or">Christos Papadimitriou</a> introduced it in the same paper that introduced PPAD and PPA. PPP contains both <a href="/facts/PPAD/EKaF3W9c">PPAD</a> and PWPP (polynomial weak pigeonhole principle) as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as <a href="/facts/One-way_function/rGtcumDW">one-way permutations</a> and <a href="/facts/Collision_resistance/8eBxsuHe">collision-resistant hash functions</a>. </p>