Sorting by Strip Swaps is NP-Hard
Created by
- Haebom
Category
Empty
저자
Swapnoneel Roy, Asai Asaithambi, Debajyoti Mukhopadhyay
개요
Sorting by Strip Swaps (SbSS)가 NP-hard임을 Block Sorting의 다항식 시간 감소를 통해 증명한다. 핵심 아이디어는 감소하는 인접성을 가드된 삼중항으로 대체하는 국소 가젯인 '케이지'를 사용하는 것이다. 인접한 케이지를 연결하고 정확히 두 개의 인접성을 제거하는 strip swap이 소스 순열에서 정확히 하나의 감소하는 인접성을 제거하는 block move에 해당하는 것을 보장하는 작은 '힌지' 가젯이 사용된다. 이로써 정확한 SbSS 일정과 완벽한 블록 일정 간의 명확한 등가성이 확립되어 NP-hardness가 증명된다.
시사점, 한계점
•
SbSS 문제의 NP-hardness를 증명.
•
Block Sorting 문제와의 연관성을 제시.
•
새로운 가젯(cage, hinge)을 개발하여 복잡한 문제를 해결.
•
NP-hardness 증명에 국한되며, 실제 문제 해결을 위한 알고리즘 개발에는 추가 연구 필요.
•
구체적인 적용 사례나 실제 데이터에 대한 실험 결과는 제시되지 않음.
