참고 요청 : 토요일의 위상 전환

Question

이것은 기술적 인 질문이 아니며,이 커뮤니티는 그러한 질문을위한 공간이 있기를 바랍니다. 그러나 이것은 부적절한 경우를 대비하여 삭제할 것입니다.

그것은 실험적으로 관찰되었습니다 (예 : 여기에 다음과 같은 프로세스로 $ 3 $ -sat 공식을 선택할 때 ).

입력 $ (n, \ alpha n) $ : $ \ alpha n $ 절을 선택하십시오. $ 3 $ 리터럴을 $ x_1, \ ldots, x_n $ 에서 무작위로 무작위로 무작위로 이와 같은 조항의 결합을 반환합니다.

출력 된 수식이 충족 할 수있는 확률은 $ \ alpha $ : $ \ alpha \ ll c $ 확률은 $ 1 $ 에 매우 가깝고 $ \ alpha \ gg c $ 확률은 $ 0 $ 에 매우 가깝습니다 (일반 $ k $ -sat 인스턴스는 관찰되었습니다. ).

내 질문은이 문제에 대한 이론적 인 이해가 무엇입니까? 내 지식의 최선을 다하여 다른 문제에 대해서는 비슷한 주장을 쉽게 증명할 수 있습니다 (예 : 임의의 그래프 $ g (n, p) $ 의 확률은 $ 4 $ 은 거의 $ 1 $ $ p (n)=omega (n {--2/3}) $ 은 거의 $ 0 $ $ p (n)= o (n ^ {- 2/3}) $ 이며 두 번째 순간의 기본 사용으로 입증 될 수 있습니다).

그러나 SAT에 대해서는 증거를 찾을 수 있습니다. 이 문제의 진전을 알고 있습니까?

Answer 1

가장 관련성있는 두 가지 엄격한 결과는 다음과 같습니다.

1. ehud friedgut, 그래프 속성의 날카로운 임계 값과 $ k $ -sat 문제점 . 이 백서 (Jean Bourgain의 부록 포함)는 $ k $ -sat가 날카로운 임계 값을 나타냅니다. 그러나 선험적이 임계 값은 $ N $ (즉,이 메서드는 $ \ alpha $ 은 일정합니다.
2. jian ding, allan sly, nike sun, 큰 $ k $ . 저자는 $ k \ geq k_0 $ 의 $ \ alpha $ 의 정확한 값을 결정합니다. $ \ alpha $ 의이 값은 캐비티 방법을 사용하여 물리학 자에 의해 계산되었지만, 그들의 논쟁은 엄격하지 않습니다.

관련 작업은 $ k $ - 다양한 임계 값 주위의 솔루션 공간의 기하학적 구조를 논의합니다. 예를 들어 DimitRis Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, 무작위 제약 만족도 문제의 솔루션 공간 기하학 .