부분집합 합 문제의 일반화된 감산 알고리즘 = A Generalized Subtractive Algorithm for Subset Sum Problem

다국어 초록 (Multilingual Abstract)

This paper presents a subset sum problem (SSP) algorithm which takes the time complexity of   log. The SSP can be classified into either super-increasing sequence or random sequence depending on the element of Set  . Additive algorithm that runs in  log has already been proposed to and utilized for the super-increasing sequence SSP, but exhaustive Brute-Force method with time complexity of    remains as the only viable algorithm for the random sequence SSP, which is thus considered NP-complete. The proposed subtractive algorithm basically selects a subset  comprised of values lower than target value , then sets the subset sum less the target value as the Residual r, only to remove from  the maximum value among those lower than  . When tested on various super-increasing and random sequence SSPs, the algorithm has obtained optimal solutions running less than the cardinality of  . It can therefore be used as a general algorithm for the SSP.

국문 초록 (Abstract)

본 논문은 부분집합 합 문제의 해를 수행 복잡도   log으로 얻는 알고리즘을 제안하였다. SSP는 집합  의원소가 초증가수열과 랜덤수열로 구성된 경우로 구분된다. 초증가수열 SSP의 해를 구하는 알고리즘은 수행 복잡도  log의 가산 알고리즘 (Additive Algorithm)이 제안되었다. 그러나 랜덤수열 SSP의 해를 구하는 알고리즘은  의 가능한 모든 경우수를 확인하는 Brute-Force 방법으로 수행 복잡도는   만이 알려져 있다. 결국, SSP는NP-완전 (NP-Complete) 문제로 알려져 있다. 본 논문은 초증가수열과 랜덤수열 SSP에 대해 수행 복잡도   log으로 해를 구하는 감산 알고리즘 을 제안하였다. 기존 개념은 목표 값 보다 작은 값으로 구성된 부분집합 에 대해 부분집합의 합에서 목표값을 뺀 값을 잉여량 (Residual, r)으로 하여 잉여량 보다 작은 값들 중 최대 값을 에서 제거하는방법을 적용하였다. 제안된 알고리즘을 다양한 초증가수열과 랜덤수열 SSP에 적용한 결과 의 원소 개수보다 적은 수행횟수로 해를 빠르게 얻는데 성공하였다. 결국, 제안된 알고리즘은 SSP의 해를 얻는 일반적인 알고리즘으로 적용할 수있을 것이다.

참고문헌 (Reference)

1 D. Nacin, "The Subset-Sum Problem" William Paterson University 2008

2 J. Bakker, "The Knapsack Problem and The LLL Algorithm"

3 R. J. W. James, "Techniques for solving subset sum problems within a given tolerance" Wiley 12 (12): 437-453, 2005

4 S. K. Chong, "On Pedagogically Sound Examples in Public-key Cryptography" 48 (48): 63-68, 2006

5 C. Blair, "Notes on Cryptography" University of Illinois 1994

6 Wikipedia, "NP-Complete" Wikimedia Foundation Inc

7 G. Fee, "Math 342: Elementary Number Theory" SFU 2000

8 Wikipedia, "List of Knapsack Problems" Wikimedia Foundation Inc

9 J. C. Gao, "Introduction to Knapsack Cipher"

10 T. H. Cormen, "Introduction to Algorithms" McGrew-Hill Book Company 2005

11 R. Merkle, "Hiding information and signatures in trapdoor knapsacks" Institute of Electrical and Electronics Engineers (IEEE) 24 (24): 525-530, 1978

12 B. Ho, "Further Exploration in Public Key Encryption" 2000

13 A. Moffat, "Example for the book "Programming, Problem Solving, and Abstraction with C" Pearson Sprint 2003

14 C. Christensen, "Cryptology: The Knapsack Problem" Northern Kentucky University 2005

15 A. Yasinsac, "Cryptography: Public Key Algorithm Cryptography based on the Knapsack Problem" University of South Alabama 2008

16 B, "Cryptography Again: Algorithmic Problem Solving" The University of Melbourne 2008

17 F. R. Dogar, "Connection Preemption in Multi-Class Networks" 2006

18 C. Umans, "Computer Science" California Institute of Technology 2008

19 K. Scott, "CS 413, Computer and Data Security: The Knapsack Problem and Merkle Hellman Encryption"

20 G. J. Woeginger, "CO2a: Combinatorial Optimization -Open Problems Around Exact Algorithms" TU Eindhoven 2008