Sign In

Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems

μž‘μ„±μž
  • Haebom
μΉ΄ν…Œκ³ λ¦¬
Empty

μ €μž

Xi-Wei Pan, Shi-Wen An, Jin-Guo Liu

πŸ’‘ κ°œμš”

λ³Έ μ—°κ΅¬λŠ” NP-λ‚œν•΄ μ΅œμ ν™” 문제 ν•΄κ²°μ˜ 병λͺ© ν˜„μƒμ„ κ·Ήλ³΅ν•˜κΈ° μœ„ν•΄, λ‹€μ–‘ν•œ μ’…λ₯˜μ˜ λ¬Έμ œλ“€μ„ νŠΉμ • 솔버에 맞게 μžλ™ λ³€ν™˜ν•˜λŠ” μžλ™ ν™˜μ›(reduction) 라이브러리 ꡬ좕을 μ œμ•ˆν•©λ‹ˆλ‹€. 이λ₯Ό μœ„ν•΄ AI μ½”λ”© μ—μ΄μ „νŠΈλ₯Ό ν™œμš©ν•œ ν•˜λ„€μŠ€ μ—”μ§€λ‹ˆμ–΄λ§(harness engineering) 기법을 λ„μž…ν•˜μ—¬, μ½”λ“œ κΈ°μ—¬, λ‹€μΈ΅ 검증, μžλ™ν™”λœ νŒŒμ΄ν”„λΌμΈμ„ κ΅¬μΆ•ν–ˆμŠ΅λ‹ˆλ‹€. μ•½ 3κ°œμ›”κ°„ 100개 μ΄μƒμ˜ 문제 μœ ν˜•κ³Ό 200개 μ΄μƒμ˜ ν™˜μ› κ·œμΉ™μ„ ν¬ν•¨ν•˜λŠ” 17만 라인의 Rust μ½”λ“œλ‘œ κ΅¬μ„±λœ 라이브러리λ₯Ό μ„±κ³΅μ μœΌλ‘œ κ°œλ°œν–ˆμŠ΅λ‹ˆλ‹€.

πŸ”‘ μ‹œμ‚¬μ  및 ν•œκ³„

β€’
AIλ₯Ό ν™œμš©ν•œ λŒ€κ·œλͺ¨ μ†Œν”„νŠΈμ›¨μ–΄ 개발 κ°€λŠ₯μ„± μž…μ¦: ν•˜λ„€μŠ€ μ—”μ§€λ‹ˆμ–΄λ§μ„ 톡해 AI μ½”λ”© μ—μ΄μ „νŠΈκ°€ 도메인 μ „λ¬Έκ°€μ˜ μ°Έμ—¬λ₯Ό μœ λ„ν•˜κ³ , 닀측적 검증을 거쳐 κ³ ν’ˆμ§ˆμ˜ μ†Œν”„νŠΈμ›¨μ–΄λ₯Ό 기쑴의 ν™˜μ› 라이브러리 ꡬ좕 λ…Έλ ₯보닀 훨씬 λΉ λ₯΄κ³  λŒ€κ·œλͺ¨λ‘œ κ°œλ°œν•  수 μžˆμŒμ„ λ³΄μ—¬μ€λ‹ˆλ‹€.
β€’
ν™˜μ› κ·Έλž˜ν”„μ˜ ν™•μž₯μ„± 및 μžλ™ν™”λœ 솔버 톡합: κ΅¬μΆ•λœ ν™˜μ› κ·Έλž˜ν”„λŠ” 전이적(transitive)으둜 κ΅¬μ„±λ˜μ–΄, μƒˆλ‘œμš΄ 솔버가 단일 문제 μœ ν˜•μ— λŒ€ν•΄ λ“±λ‘λ˜λ©΄ μ—°κ²°λœ λͺ¨λ“  문제 μœ ν˜•μ— μžλ™μœΌλ‘œ 적용될 수 μžˆμŠ΅λ‹ˆλ‹€. μ΄λŠ” λ‹€μ–‘ν•œ μ’…λ₯˜μ˜ ν•˜λ“œν•œ λ¬Έμ œλ“€μ„ 효율적으둜 ν•΄κ²°ν•  수 μžˆλŠ” κΈ°λ°˜μ„ λ§ˆλ ¨ν•©λ‹ˆλ‹€.
β€’
ν•˜λ„€μŠ€ μ—”μ§€λ‹ˆμ–΄λ§μ˜ μΌλ°˜ν™” 및 λ³΅μž‘μ„±: μ œμ•ˆλœ ν•˜λ„€μŠ€ μ—”μ§€λ‹ˆμ–΄λ§ μ ‘κ·Ό 방식은 νš¨κ³Όμ μ΄μ—ˆμ§€λ§Œ, λ‹€μ–‘ν•œ μ’…λ₯˜μ˜ AI μ—μ΄μ „νŠΈμ™€ 문제 μœ ν˜•μ— λŒ€ν•΄ 이λ₯Ό μΌλ°˜ν™”ν•˜κ³  μ΅œμ ν™”ν•˜λŠ” λ°λŠ” 좔가적인 연ꡬ가 ν•„μš”ν•  수 μžˆμŠ΅λ‹ˆλ‹€. λ˜ν•œ, ν™˜μ› κ·œμΉ™μ˜ λ³΅μž‘μ„±κ³Ό 검증 κ³Όμ •μ˜ 정ꡐ함이 전체 μ‹œμŠ€ν…œμ˜ μ„±λŠ₯에 큰 영ν–₯을 λ―ΈμΉ  수 μžˆμŠ΅λ‹ˆλ‹€.
πŸ‘
Made with Slashpage