3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- PCP 갭 재정식화 경로
PCP 정리 덕분에 P≠NP 는 「특정 갭-CSP 를 다항 시간에 푸는 알고리즘이 존재하지 않는다」는 강건한 명제와 정확히 같다는 점을 표적으로 삼아, 갭을 다루는 PCP·UGC 계열 도구로 「어떤 갭 구간까지의 난해성이 어떤 하한 기법과 접속 가능한가」를 체계적으로 규명하자는 아이디어다.
- 희소집합 붕괴 판정 경로
Berman–Hartmanis 동형 추측과, Mahaney 정리 같은 희소집합 붕괴 정리, Ladner 정리가 보인 NP 내부 차수 구조(조밀한 상반격자)를 「P=NP 라면 성립할 수 없는(혹은 반드시 성립해야 하는) 구조적 성질의 목록」으로 통합하고, 환원 유형 × 희소성·구조 수준 격자의 미해결 칸을 한 칸씩 메우자는 구조 복잡도 아이디어다.
- 자기환원 체커 경로
SAT 의 하향 자기 환원성과 프로그램 체킹·자기 교정·산술화 같은 검증 장치를 「P=NP 세계가 반드시 만족해야 하는 구조적 제약 조건의 추출기」로 재해석하고, 대화형 증명이 NEXP/MA 수준에서 낸 무조건적 하한 전선을 NP 쪽으로 한 단계씩 끌어내리자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.