合数问题询问对于给定的正整数 
，是否存在正整数 
和 
使得 
。
合数问题的复杂性多年来一直未知，尽管已知该问题属于 
(Pratt 1975, Garey and Johnson 1983)。Agrawal et al. (2004) 随后出人意料地发现了一种多项式时间算法，现在称为 AKS 素性测试。
合数问题
参见
AKS 素性测试, 合数使用 Wolfram|Alpha 探索
参考文献
Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-157 和 288, 1983。Miller, G. "Riemann's Hypothesis and Tests for Primality." J. Comp. Syst. Sci. 13, 300-317, 1976。Pratt, V. "Every Prime Has a Succinct Certificate." SIAM J. Comput. 4, 214-220, 1975。请引用为
Weisstein, Eric W. "合数问题。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CompositeNumberProblem.html