3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- 카운팅 프레게 하한 공략
Cook–Reckhow 사다리에서 Resolution·AC0-Frege 다음 칸인 AC0[p]-Frege 가 30년 넘게 정체된 원인을 회로 하한 기법을 증명 체계 하한으로 이식하는 일반 원리의 부재로 보고, 다항식 계산법의 차수 하한·질의-통신 리프팅·증명 복잡도 생성기를 결합해 공략하자는 아이디어다.
- SoS 하한 알고리즘 배제
「다항 시간 알고리즘 전부」를 배제하기 전 단계로, 스펙트럴 방법·LP·SDP 완화·대다수 근사 알고리즘을 포섭하는 Sum-of-Squares 위계에 대한 무조건적 하한들을 P vs NP 공략의 부품으로 재조립하자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.