정수 관계에 대한 (작은) 솔루션이 답을 얻을 수 있도록 부분 집합 합 또는 숫자 분할 문제의 인스턴스를 인코딩하는 방법이 있습니까? 확실하지 않다면 어떤 확률 론적 의미에서?
선택한 숫자의 범위가 보다 큰 ‘저밀도’영역에서 LLL (및 아마도 PSLQ)이 부분 집합 합계 문제를 해결하는 데 적당히 사용되었다는 것을 알고 있습니다. 선택된 숫자의 범위가 보다 훨씬 작을 때 더 큰 크기의 인스턴스로 ‘고밀도’영역에서 실패합니다 . 여기서 저밀도 및 고밀도는 솔루션 수를 나타냅니다. 저밀도 영역은 존재하는 솔루션이 거의 없거나 전혀없는 반면, 고밀도는 솔루션이 많은 영역을 나타냅니다.2 N
2N2N
고밀도 영역에서 LLL은 주어진 인스턴스간에 (작은) 정수 관계를 발견하지만 인스턴스 크기가 증가함에 따라 실행 가능한 서브 세트 합 또는 숫자 분할 문제 솔루션 인 관계가 발견 될 확률은 점점 작아집니다.
정수 관계 감지는 최적의 지수 범위 내에서 다항식이지만 Subset Sum 및 NPP는 분명히 NP-Complete이므로 일반적으로 불가능할 수 있지만 인스턴스가 무작위로 균일하게 그려지면 더 간단해질 수 있습니까?
아니면이 질문을하지 말고 대신 계산의 기하 급수적으로 증가하는 대신 최적의 대답에서 지수를 줄이는 방법이 있는지 묻어 야합니까?
답변
m을 가장 큰 숫자의 로그라고하자. 경우 그것은 동적 프로그래밍을 이용하여 다항식 시간 내에 해결 가능하다. 일반적으로, 적어도 모든 알려진 알고리즘 인출 Ω ( 2 m ) 의 시간. m = ω ( log n ) 및 m = o ( n ) 인 경우 알려진 다항식 시간 알고리즘이 없습니다.
미디엄=영형(로그엔)Ω(2미디엄)
미디엄=ω(로그엔)
미디엄=영형(엔)
그러나 Flaxman과 Przydatek는 예상 다항식 시간의 중간 밀도 부분 집합 합 문제를 해결하는 알고리즘을 제공합니다.
이 참조를 확인하십시오.