3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- KW 게임 리프팅 공략
회로 깊이를 두 참가자의 통신 복잡도와 정확히 대응시키는 Karchmer–Wigderson 게임과 리프팅 정리의 결합이 단조 회로 세계에서 거둔 성공을 일반 회로 쪽으로 밀어붙여, KRW 추측의 부분 사례를 공략하고 P 와 NC1 분리로 가는 교두보를 만들자는 아이디어다.
- 정보 병목 엔트로피 경로
통신 복잡도에서 성숙한 정보 복잡도 도구를 회로 자체에 이식해, 회로의 절단을 가로지르는 정보량으로 「정보 흐름 병목」 측도를 정의하고 압축 모순으로 회로 하한을 얻는 경로를 설계하자는 아이디어다. Razborov 의 열등모듈러 측도 한계를 깨는 측도 설계가 중심 문제다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.