3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- 부정 제한 회로 하한 증폭
부정(NOT) 게이트를 O(log n)개까지 허용한 회로에서 NP 완전 문제의 초다항 크기 하한을 보이면 일반 회로 하한이 되어 P≠NP 가 따라온다는 점에 착안해, 부정 게이트 수 t 를 독립된 계산 자원으로 보고 현재 약 (1/6)log log n 수준인 최전선을 점진적으로 밀어 올리자는 아이디어다.
- 행렬 강성 재건 경로
Valiant 의 행렬 강성 프로그램에서 유력 후보들이 잇따라 비강성으로 판명된 결과를 실패가 아닌 후보 선별 필터로 재해석해 「강성 후보가 가져서는 안 되는 성질」 목록을 정식화하고, 대칭성이 파괴된 준명시적 구성에서 Valiant 문턱을 노리자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.