또 다른 스레드 에서 Joe Fitzsimons는 “3SAT에서 가장 좋은 현재 하한값”에 대해 물었습니다.
나는 다른 길로 가고 싶습니다 : 3SAT 에서 가장 좋은 현재 상한 은 무엇입니까 ? 다시 말해, 가장 효율적인 SAT 솔버의 시간 복잡성은 무엇입니까?
특히, SAT에 대한 하위 지수 (아직 초 다항식) 알고리즘을 찾는 것이 가능합니까?
답변
“최고의”SAT 솔버에는 이론 용과 연습용의 두 가지 종류가 있습니다.
이론
- Kazuo Iwama, Kazuhisa Seto, Tadashi Takai, Suguru Tamaki, ” 3-SAT를위한 개선 된 무작위 알고리즘 “, ISAAC 2010.
3SAT에 대해 무작위 화 된 .
O(1.32113n)
- Timon Hertli, Robin A. Moser, Dominik Scheder, ” 중요 변수를 사용하여 3-SAT에 대한 PPSZ 개선 “, 2011.
무작위 3SAT 대.
O(1.321n)
- Konstantin Kutzkov, Dominik Scheder, ” CSP를 사용하여 결정 론적 3-SAT 개선 “, 2010.
결정적 3SAT 대.
O(1.439n)
연습
매년 경쟁 결과는 SAT 회의 를 확인하십시오 .
답변
최대 하나의 만족스러운 할당이 있을지 여부에 관계없이
알려진 결정 론적 알고리즘보다 더 나은 범위를 갖는 SAT 에 대한 제로 오류 무작위 알고리즘 (또는 그 문제에 대한 coNE / Eadvice 알고리즘
)을 알지
못합니다.
O∼(1.3303n)
n
O(1.3071n)
O(1.4699n)
- 3-SAT 빠르고 간단한 – 일반에서 PPSZ 홀드의 고유-SAT 경계 (원래에 언급 된 것을 보여 라이언의 코멘트 )
- “
시간에 실행되는 일방적 인 오류가있는 3-SAT에 대한 무작위 알고리즘이 있습니다.
O(1.30704n)- “
시간에 실행되는 일방적 인 오류 와 함께 4-SAT에 대한 무작위 알고리즘이 있습니다
O(1.46899n)
- 고유 한 3-SAT에 대한 PPSZ 장벽을 깨는
결과는 다음과 같이 요약 될 수 있습니다.
“독특한 3-SAT에는 무작위 알고리즘이 있습니다.
ϵ=1/(1024)S
O(2(S+o(1))⋅n)
,
현재 논문의 알고리즘은 제 시간에 실행됩니다
O(2(S−ϵ+o(1))⋅n)
답변
O(an)
a=2(k−1)/k
O(1.33334n)
O(1.5n)
O((a+ϵ)n)
a
ϵ>0
O∗
답변
이미 언급했듯이 이론적 인 실행 시간 보증에 관심이 있다면이 질문은 중복됩니다.
그러나 구체적인 문제 (당신이 언급 한 채색 문제와 같은)를 실제로 풀고 싶다면 이론적 상한을 연구하는 것이 전혀 의미가 없다고 생각합니다.
“엔지니어링”측면을 피하고 싶었지만 인기있는 SAT 솔버를 사용하여 시도해보고 어떤 일이 발생하는지 확인하십시오 (대부분 동일한 DIMACS 파일 형식을 읽을 수 있으므로 시도하기 쉽습니다). 다른 솔버). 당신은 긍정적이고 부정적인 놀라움을 모두 가질 수 있습니다. 최근에 SAT 인스턴스 제품군이있었습니다. 수만 개의 변수와 백만 개 이상의 절을 가진 많은 인스턴스는 해결하기 쉬운 것으로 판명되었지만 수백 개의 변수와 수천 개의 절을 가진 훨씬 간단한 인스턴스는 내가 시도한 모든 솔버에게는 너무 어려웠습니다.
답변
- Timon Hertli, ” 3-SAT 더 빠르고 간단한-PPSZ 홀드를위한 고유 한 SAT 바운드 “, FOCS 2011.
O(1.308n)
답변
지수 시간 가설 이 거짓이 아닌 한 3SAT에서 하위 지수 알고리즘을 갖는 것은 불가능합니다 .
- Kazuo Iwama, Suguru Tamaki , 2004 년 3-SAT 상한선 개선 .
O(1.324n)
- Daniel Rolf , 2005 년 3-SAT의 PPSZ / Schoning-Algorithm에 대한 향상된 바운드 .
O(1.32216n)