3-1
도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- SAT 상계 사다리 전략
3-SAT 지수 상계의 밑수가 전수탐색 2^n 에서 꾸준히 내려온 이력을 하나의 사다리로 보고, 밑수 끌어내리기·CSP 이분법의 다항 시간 섬 확장·SETH/ETH 반증 시도라는 3중 경로를 제안한다. 부분 성공이 회로 클래스 SAT 의 가속으로 이어지면 Williams 의 연결로 회로 하한 쪽 성과도 된다는 아이디어다(3-SAT·k-SAT 밑수 개선만으로는 새 하한을 주지 않는다).
- SAT 시공간 하한 강화
아무 가정 없이 성립하는 몇 안 되는 하한인 SAT 의 시간-공간 트레이드오프 하한(현재 지수 2cos(pi/7) 약 1.8019)에 새 속도향상·감속 규칙과 비상대화 성분을 더해 지수 한계를 밀어 올리고, 궁극적으로 임의의 상수 c 에 대한 하한과 L ≠ NP 를 향하자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.