3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- 해공간 상전이 OGP 경로
랜덤 k-SAT 해공간의 기하적 성질만으로 넓은 알고리즘 클래스의 실패를 무조건 증명하는 overlap gap property(OGP)를 「해공간 기하 → 알고리즘 클래스 배제」 함수로 보고, 배제되는 클래스를 P 에 가깝게 넓히는 사다리와 평균 사례에서 최악 사례로 가는 통로의 지도를 함께 만들자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.