Numerical 3-dimensional matching

<p>Numerical 3-dimensional matching is an <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> decision problem. It is given by three <a href="/facts/Multisets/bPFJGMDo">multisets</a> of <a href="/facts/Integer/PUwwrawx">integers</a> 
  
    
      
        X
      
    
    {\displaystyle X}
  
, 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 and 
  
    
      
        Z
      
    
    {\displaystyle Z}
  
, each containing 
  
    
      
        k
      
    
    {\displaystyle k}
  
 elements, and a bound 
  
    
      
        b
      
    
    {\displaystyle b}
  
. The goal is to select a subset 
  
    
      
        M
      
    
    {\displaystyle M}
  
 of 
  
    
      
        X
        ×
        Y
        ×
        Z
      
    
    {\displaystyle X\times Y\times Z}
  
 such that every integer in 
  
    
      
        X
      
    
    {\displaystyle X}
  
, 
  
    
      
        Y
      
    
    {\displaystyle Y}
  
 and 
  
    
      
        Z
      
    
    {\displaystyle Z}
  
 occurs exactly once and that for every triple 
  
    
      
        (
        x
        ,
        y
        ,
        z
        )
      
    
    {\displaystyle (x,y,z)}
  
 in the subset 
  
    
      
        x
        +
        y
        +
        z
        =
        b
      
    
    {\displaystyle x+y+z=b}
  
 holds.
This problem is labeled as [SP16] in.
</p>

Numerical 3-dimensional matching open-in-new

Numerical 3-dimensional matching