PPP (complexity)

<h2 id="definition">Definition</h2>
<p>PPP is the set of all function computation problems that admit a <a href="/facts/Polynomial-time_reduction/bBvfFxyM">polynomial-time reduction</a> to the <i>PIGEON</i> problem, defined as follows:
</p>
Given a Boolean circuit 
  
    
      
        C
      
    
    {\displaystyle C}
  
 having the same number 
  
    
      
        n
      
    
    {\displaystyle n}
  
 of input bits as output bits, find either an input 
  
    
      
        x
      
    
    {\displaystyle x}
  
 that is mapped to the output 
  
    
      
        C
        (
        x
        )
        =
        
          0
          
            n
          
        
      
    
    {\displaystyle C(x)=0^{n}}
  
, or two distinct inputs 
  
    
      
        x
        ≠
        y
      
    
    {\displaystyle x\neq y}
  
 that are mapped to the same output 
  
    
      
        C
        (
        x
        )
        =
        C
        (
        y
        )
      
    
    {\displaystyle C(x)=C(y)}
  
.
<p>A problem is PPP-<a href="/facts/Complete_(complexity)/Ine1b8Qy">complete</a> if <i>PIGEON</i> is also polynomial-time reducible to it. Note that the pigeonhole principle guarantees that <i>PIGEON</i> is total. We can also define <i>WEAK-PIGEON</i>, for which the
weak pigeonhole principle guarantees totality. PWPP is the corresponding class of problems that are polynomial-time reducible to it.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> <i>WEAK-PIGEON</i> is the following problem:
</p>
Given a Boolean circuit 
  
    
      
        C
      
    
    {\displaystyle C}
  
 having 
  
    
      
        n
      
    
    {\displaystyle n}
  
 input bits and 
  
    
      
        n
        −
        1
      
    
    {\displaystyle n-1}
  
 output bits, find 
  
    
      
        x
        ≠
        y
      
    
    {\displaystyle x\neq y}
  
 such that 
  
    
      
        C
        (
        x
        )
        =
        C
        (
        y
        )
      
    
    {\displaystyle C(x)=C(y)}
  
.
<p>Here, the range of the circuit is strictly smaller than its domain, so the circuit is guaranteed to be non-<a href="/facts/Injective_function/5ES6tqf5">injective</a>. <i>WEAK-PIGEON</i> reduces to <i>PIGEON</i> by appending a single 1 bit to the circuit's output, so PWPP 
  
    
      
        ⊆
      
    
    {\displaystyle \subseteq }
  
 PPP.
</p>
<h2 id="connection-to-cryptography">Connection to cryptography</h2>
<p>We can view the circuit in <i>PIGEON</i> as a polynomial-time computable hash function. Hence, PPP is the complexity class which captures the hardness of either inverting or finding a collision in hash functions. More generally, the relationship of subclasses of <a href="/facts/FNP_(complexity)/m4MVkn3w">FNP</a> to polynomial-time complexity classes can be used to determine the existence of certain cryptographic primitives, and vice versa.
</p><p>For example, it is known that if FNP = <a href="/facts/Function_problem/3zPWpraL">FP</a>, then <a href="/facts/One-way_functions/rGtcumDW">one-way functions</a> do not exist. Similarly, if PPP = FP,
then one-way permutations do not exist.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Hence, PPP (which is a subclass of FNP) more closely captures the question of the existence of one-way permutations. We can prove this by reducing the problem of inverting a permutation 
  
    
      
        π
      
    
    {\displaystyle \pi }
  
 on an output 
  
    
      
        y
      
    
    {\displaystyle y}
  
 to <i>PIGEON</i>. Construct a circuit 
  
    
      
        C
      
    
    {\displaystyle C}
  
 that computes 
  
    
      
        C
        (
        x
        )
        =
        π
        (
        x
        )
        ⊕
        y
      
    
    {\displaystyle C(x)=\pi (x)\oplus y}
  
. Since 
  
    
      
        π
      
    
    {\displaystyle \pi }
  
 is a permutation, a solution to <i>PIGEON</i> must output 
  
    
      
        x
      
    
    {\displaystyle x}
  
 such that 
  
    
      
        C
        (
        x
        )
        =
        0
        =
        π
        (
        x
        )
        ⊕
        y
      
    
    {\displaystyle C(x)=0=\pi (x)\oplus y}
  
, which implies 
  
    
      
        π
        (
        x
        )
        =
        y
      
    
    {\displaystyle \pi (x)=y}
  
.
</p>
<h2 id="relationship-to-ppad">Relationship to PPAD</h2>
<p>PPP contains <a href="/facts/PPAD/EKaF3W9c">PPAD</a> as a subclass (strict containment is an open problem). This is because <i>End-of-the-Line</i>, which defines PPAD, admits a straightforward polynomial-time reduction to <i>PIGEON</i>. In <i>End-of-the-Line</i>, the input is a start vertex 
  
    
      
        s
      
    
    {\displaystyle s}
  
 in a directed graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 where each vertex has at most one successor and at most one predecessor, represented by a polynomial-time computable successor function 
  
    
      
        f
      
    
    {\displaystyle f}
  
. Define a circuit 
  
    
      
        C
      
    
    {\displaystyle C}
  
 whose input is a vertex 
  
    
      
        x
      
    
    {\displaystyle x}
  
 and whose output is its successor if there is one, or 
  
    
      
        x
      
    
    {\displaystyle x}
  
 if it does not. If we represent the source vertex 
  
    
      
        s
      
    
    {\displaystyle s}
  
 as the bitstring 
  
    
      
        
          0
          
            n
          
        
      
    
    {\displaystyle 0^{n}}
  
, this circuit is a direct reduction of <i>End-of-the-Line</i> to <i>Pigeon</i>, since any collision in 
  
    
      
        C
      
    
    {\displaystyle C}
  
 provides a sink in 
  
    
      
        G
      
    
    {\displaystyle G}
  
.
</p>
<h2 id="notable-problems">Notable problems</h2>
<h3>Equal sums problem</h3>
<p>The equal sums problem is the following problem. Given 
  
    
      
        n
      
    
    {\displaystyle n}
  
 positive integers that sum to less than 
  
    
      
        
          2
          
            n
          
        
        −
        1
      
    
    {\displaystyle 2^{n}-1}
  
, find two distinct subsets of the integers that have the same total. This problem is contained in PPP, but it is not known if it is PPP-complete.
</p>
<h3>Constrained-SIS problem</h3>
<p>The constrained-SIS (short integer solution) problem, which is a generalization of the <a href="/facts/Short_integer_solution_problem/Qvx0TSoY">SIS problem</a> from lattice-based cryptography, has been shown to be complete for PPP.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> Prior to that work, the only problems known to be complete for PPP were variants of <i>PIGEON</i>.
</p>
<h3>Integer factorization</h3>
<p>There exist polynomial-time randomized reductions from the <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> problem to <i>WEAK-PIGEON</i>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> Additionally, under the <a href="/facts/Generalized_Riemann_hypothesis/17nLmBbu">generalized Riemann hypothesis</a>, there also exist deterministic polynomial reductions. 
However, it is still an open problem to unconditionally show that integer factorization is in PPP.
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Christos Papadimitriou (1994). "On the complexity of the parity argument and other inefficient proofs of existence" (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Archived from the original (PDF) on 2016-03-04. Retrieved 2009-12-11. <a href="https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" target="_blank">https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Emil Jeřábek (2016). "Integer factoring and modular square roots". Journal of Computer and System Sciences. 82 (2): 380–394. arXiv:1207.5220. doi:10.1016/j.jcss.2015.08.001. <a href="/wiki/Journal_of_Computer_and_System_Sciences" target="_blank">/wiki/Journal_of_Computer_and_System_Sciences</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Christos Papadimitriou (1994). "On the complexity of the parity argument and other inefficient proofs of existence" (PDF). Journal of Computer and System Sciences. 48 (3): 498–532. doi:10.1016/S0022-0000(05)80063-7. Archived from the original (PDF) on 2016-03-04. Retrieved 2009-12-11. <a href="https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" target="_blank">https://web.archive.org/web/20160304084618/http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>K. Sotiraki, M. Zampitakis, and G. Zirdelis (2018). "PPP-Completeness with Connections to Cryptography". Proc. of 59th Symposium on Foundations of Computer Science. pp. 148–158. arXiv:1808.06407. doi:10.1109/FOCS.2018.00023.{{cite conference}}:  CS1 maint: multiple names: authors list (link) <a href="/wiki/Symposium_on_Foundations_of_Computer_Science" target="_blank">/wiki/Symposium_on_Foundations_of_Computer_Science</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Emil Jeřábek (2016). "Integer factoring and modular square roots". Journal of Computer and System Sciences. 82 (2): 380–394. arXiv:1207.5220. doi:10.1016/j.jcss.2015.08.001. <a href="/wiki/Journal_of_Computer_and_System_Sciences" target="_blank">/wiki/Journal_of_Computer_and_System_Sciences</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

PPP (complexity) open-in-new

PPP (complexity)