3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- 무패딩 곱셈도 GCT
BIP(2016)의 부정 결과는 「패딩 + 발생 장애물」 조합을 막았을 뿐이라고 보고, 비교 대상을 패딩이 필요 없는 동차 모델(IMM·행렬 거듭제곱) 대 permanent 로 바꾸고 장애물을 곱셈도 격차 부등식으로 올리는 수정 GCT 경로를 제안하는 아이디어다.
- 상수깊이 하한 부트스트랩
Limaye–Srinivasan–Tavenas(2021)의 상수 깊이 산술 회로 초다항 하한을 퍼머넌트 같은 VNP 다항식에 대해 깊이 축소 문턱까지 끌어올려 VP≠VNP 를 노리고, 그 대수적 분리를 불리언 세계로 옮길 다리를 찾는 2단 파이프라인을 설계해 어느 연결부가 진짜 병목인지 정량화하자는 아이디어다. 대수 분리에서 불리언 분리로 가는 알려진 연결은 모두 반대 방향이라 2단은 미해결 문제다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.