ในทฤษฎีจำนวนความซับซ้อนของจำนวนเต็มคือ จำนวนเลขหนึ่ง ที่น้อยที่สุด ที่สามารถใช้แทนจำนวนนั้นได้ โดยใช้เลขหนึ่งและการบวก การคูณ และวงเล็บจำนวนใดๆ ก็ได้ โดยความซับซ้อนนี้จะอยู่ภายในค่าคงที่ของลอการิทึมของจำนวนเต็มที่ กำหนด เสมอ

ตัวอย่างเช่น เลข 11 อาจแทนด้วยเลข 1 จำนวน 8 ตัว:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1

อย่างไรก็ตาม ไม่มีตัวแทนใดที่ใช้เลขเจ็ดหรือน้อยกว่านั้น ดังนั้น ความซับซ้อนของมันจึงเท่ากับ 8

ความซับซ้อนของตัวเลข 1, 2, 3, ... คือ

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (ลำดับA005245ในOEIS )

ตัวเลขที่เล็กที่สุดที่มีความซับซ้อน 1, 2, 3, ... คือ

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (ลำดับA005520ในOEIS )

คำถามเกี่ยวกับการแสดงจำนวนเต็มในลักษณะนี้ได้รับการพิจารณาครั้งแรกโดยMahler & Popken (1953)พวกเขาถามถึงจำนวนที่ใหญ่ที่สุดที่มีความซับซ้อนkที่ กำหนด ^{[ 1 ]}ต่อมา Selfridge แสดงให้เห็นว่าจำนวนนี้คือ

${\displaystyle 2^{x}3^{(k-2x)/3}{\text{ โดยที่ }}x=-k{\bmod {3}}.}$

ตัวอย่างเช่น เมื่อk = 10 , x = 2และจำนวนเต็มที่มากที่สุดที่สามารถแสดงได้โดยใช้เลข 1 สิบตัวคือ2 ² 3 ² = 36การแสดงออกของมันคือ

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1)

ดังนั้น ความซับซ้อนของจำนวนเต็มnมีค่าอย่างน้อย3 log nความซับซ้อนของnมีค่ามากที่สุด3 log n (ประมาณ4.755 log n ): สามารถหาการแสดงออกที่มีความยาวนี้สำหรับn ได้โดยการใช้ วิธีของ Hornerกับการแสดงเลขฐานสองของn [ ^{2 ] จำนวนเต็มเกือบทั้งหมดมีการแสดงที่มี ความ}ยาวจำกัดด้วยลอการิทึมที่มีค่าคงที่น้อยกว่า คือ^3.529 log n ^{[ 3} ]

ความซับซ้อนของจำนวนเต็มทุกจำนวนnจนถึงเกณฑ์N บางค่า สามารถคำนวณได้ในเวลารวมO ( N ^1.222911236 ) ^{[ 4 ]}ซึ่งได้รับการปรับปรุงให้เป็นอัลกอริทึมเวลาโดย He ^{[ 5 ]}ความซับซ้อนของจำนวนเต็มตัวเดียวสามารถคำนวณได้ในเวลาต่ำกว่าเชิงเส้นเช่น กัน${\displaystyle \|n\|}$${\displaystyle O(n\log ^{O(1)}n)}$${\displaystyle n}$${\displaystyle O(n^{0.6514})}$

อัลกอริทึมสำหรับการคำนวณความซับซ้อนของจำนวนเต็มถูกนำมาใช้เพื่อหักล้างข้อสันนิษฐาน หลายประการ เกี่ยวกับความซับซ้อน โดยเฉพาะอย่างยิ่ง ไม่จำเป็นเสมอไปที่การแสดงออกที่เหมาะสมที่สุดสำหรับจำนวนnจะได้มาจากการลบหนึ่งออกจากnหรือโดยการแสดงnเป็นผลคูณของตัวประกอบที่เล็กกว่าสองตัว ตัวอย่างที่เล็กที่สุดของจำนวนที่มีการแสดงออกที่เหมาะสมที่สุดไม่ได้อยู่ในรูปแบบนี้คือ 353942783 ซึ่งเป็นจำนวนเฉพาะและด้วยเหตุนี้จึงหักล้างข้อสันนิษฐานของRichard K. Guyที่ว่าความซับซ้อนของจำนวนเฉพาะp ทุกตัว คือหนึ่งบวกกับความซับซ้อนของp − 1 [ ^{6 ] ใน}ความเป็นจริง สามารถแสดงได้ว่า นอกจากนี้ Venecia Wang ^ยังให้ตัวอย่างที่น่าสนใจบางอย่าง เช่น, , , แต่^{[ 7} ]${\displaystyle \|353942783\|=\|353942782\|=63}$${\displaystyle \|743\times 2\|=\|743\|=22}$${\displaystyle \|166571\times 3\|=\|166571\|=39}$${\displaystyle \|97103\times 5\|=\|97103\|=38}$${\displaystyle \|23^{2}\|=20}$${\displaystyle 2\|23\|=22}$

• ไวส์สไตน์, เอริก ดับเบิลยู. "ความซับซ้อนของจำนวนเต็ม" . แมทเวิลด์ .