도전 아이디어
풀이에 도전하는 아이디어. 누구나 더하고, 아이디어마다 질의·보완·반론·자료를 붙입니다.
- 부정 제한 회로 하한 증폭
부정(NOT) 게이트를 O(log n)개까지 허용한 회로에서 NP 완전 문제의 초다항 크기 하한을 보이면 일반 회로 하한이 되어 P≠NP 가 따라온다는 점에 착안해, 부정 게이트 수 t 를 독립된 계산 자원으로 보고 현재 약 (1/6)log log n 수준인 최전선을 점진적으로 밀어 올리자는 아이디어다.
- 무패딩 곱셈도 GCT
BIP(2016)의 부정 결과는 「패딩 + 발생 장애물」 조합을 막았을 뿐이라고 보고, 비교 대상을 패딩이 필요 없는 동차 모델(IMM·행렬 거듭제곱) 대 permanent 로 바꾸고 장애물을 곱셈도 격차 부등식으로 올리는 수정 GCT 경로를 제안하는 아이디어다.
- 카운팅 프레게 하한 공략
Cook–Reckhow 사다리에서 Resolution·AC0-Frege 다음 칸인 AC0[p]-Frege 가 30년 넘게 정체된 원인을 회로 하한 기법을 증명 체계 하한으로 이식하는 일반 원리의 부재로 보고, 다항식 계산법의 차수 하한·질의-통신 리프팅·증명 복잡도 생성기를 결합해 공략하자는 아이디어다.
- 대칭성 사다리 협공 전략
순서 구조 위에서 FO(LFP) 와 ∃SO 를 분리하는 것은 P≠NP 와 정확히 동치라는 사실에서 출발해, 입력 구조의 자기동형군이 얼마나 풍부한지를 매개변수로 한 「대칭성 사다리」를 놓고 고대칭 쪽의 하한과 저대칭 쪽의 P 포획 결과를 양방향에서 넓혀 가자는 아이디어다.
- MCSP 증폭 삼각측량
MCSP·MKtP 에 대한 아주 약한 하한이 강한 분리로 증폭되는 현상, 원웨이 함수와 MKtP 평균적 어려움의 동치, 자연 증명적 하한이 학습 알고리즘으로 바뀌는 결과라는 세 갈래를 하나의 「삼각측량」 틀로 묶어, 증폭 문턱 바로 아래의 약한 하한과 그 앞의 지역성 장벽을 겨냥하자는 아이디어다.
- 장벽 지도화와 우회 역설계
상대화·자연 증명·대수화 세 장벽이 「증명 기법의 성질 공간」의 어디를 덮고 어디를 비워 두는지 정밀하게 지도화하고, 장벽을 실제로 뚫은 사례를 성분 분해해 세 장벽을 동시에 피하는 기법의 필요조건 목록을 역설계하자는 메타 수준 아이디어다.
- SAT 상계 사다리 전략
3-SAT 지수 상계의 밑수가 전수탐색 2^n 에서 꾸준히 내려온 이력을 하나의 사다리로 보고, 밑수 끌어내리기·CSP 이분법의 다항 시간 섬 확장·SETH/ETH 반증 시도라는 3중 경로를 제안한다. 부분 성공이 회로 클래스 SAT 의 가속으로 이어지면 Williams 의 연결로 회로 하한 쪽 성과도 된다는 아이디어다(3-SAT·k-SAT 밑수 개선만으로는 새 하한을 주지 않는다).
- 상수깊이 하한 부트스트랩
Limaye–Srinivasan–Tavenas(2021)의 상수 깊이 산술 회로 초다항 하한을 퍼머넌트 같은 VNP 다항식에 대해 깊이 축소 문턱까지 끌어올려 VP≠VNP 를 노리고, 그 대수적 분리를 불리언 세계로 옮길 다리를 찾는 2단 파이프라인을 설계해 어느 연결부가 진짜 병목인지 정량화하자는 아이디어다. 대수 분리에서 불리언 분리로 가는 알려진 연결은 모두 반대 방향이라 2단은 미해결 문제다.
- KW 게임 리프팅 공략
회로 깊이를 두 참가자의 통신 복잡도와 정확히 대응시키는 Karchmer–Wigderson 게임과 리프팅 정리의 결합이 단조 회로 세계에서 거둔 성공을 일반 회로 쪽으로 밀어붙여, KRW 추측의 부분 사례를 공략하고 P 와 NC1 분리로 가는 교두보를 만들자는 아이디어다.
- 유계 산술 독립성 경로
P≠NP 가 지금 쓰는 공리계에서 애초에 증명 가능한가라는 메타 질문을 파고들어, 유계 산술의 약한 이론들에서 회로 하한 명제의 증명 불가능성을 보인 결과(암호 가정 아래의 조건부 결과와 강한 형태의 하한 명제에 대한 무조건 결과)를 하나의 지도로 묶고, 그 경계를 한 단계 올리는 데 정확히 무엇이 필요한지 명시하자는 아이디어다. P≠NP 의 표준 형식화가 PV₁ 에서 증명 불가능한지는 아직 모른다.
- SoS 하한 알고리즘 배제
「다항 시간 알고리즘 전부」를 배제하기 전 단계로, 스펙트럴 방법·LP·SDP 완화·대다수 근사 알고리즘을 포섭하는 Sum-of-Squares 위계에 대한 무조건적 하한들을 P vs NP 공략의 부품으로 재조립하자는 아이디어다.
- 해공간 상전이 OGP 경로
랜덤 k-SAT 해공간의 기하적 성질만으로 넓은 알고리즘 클래스의 실패를 무조건 증명하는 overlap gap property(OGP)를 「해공간 기하 → 알고리즘 클래스 배제」 함수로 보고, 배제되는 클래스를 P 에 가깝게 넓히는 사다리와 평균 사례에서 최악 사례로 가는 통로의 지도를 함께 만들자는 아이디어다.
- 양자 하한의 고전 이식
양자 질의 복잡도의 다항식 방법과 어드버서리 방법이 고전 명제 증명에 산발적으로 성공해 온 사례를 「양자 측도 → 고전 하한」 이식 사전으로 체계화하고, 식 크기 하한과 KW형 통신 하한을 생산하는 두 갈래 파이프라인을 만들자는 아이디어다.
- SAT 시공간 하한 강화
아무 가정 없이 성립하는 몇 안 되는 하한인 SAT 의 시간-공간 트레이드오프 하한(현재 지수 2cos(pi/7) 약 1.8019)에 새 속도향상·감속 규칙과 비상대화 성분을 더해 지수 한계를 밀어 올리고, 궁극적으로 임의의 상수 c 에 대한 하한과 L ≠ NP 를 향하자는 아이디어다.
- 행렬 강성 재건 경로
Valiant 의 행렬 강성 프로그램에서 유력 후보들이 잇따라 비강성으로 판명된 결과를 실패가 아닌 후보 선별 필터로 재해석해 「강성 후보가 가져서는 안 되는 성질」 목록을 정식화하고, 대칭성이 파괴된 준명시적 구성에서 Valiant 문턱을 노리자는 아이디어다.
- PCP 갭 재정식화 경로
PCP 정리 덕분에 P≠NP 는 「특정 갭-CSP 를 다항 시간에 푸는 알고리즘이 존재하지 않는다」는 강건한 명제와 정확히 같다는 점을 표적으로 삼아, 갭을 다루는 PCP·UGC 계열 도구로 「어떤 갭 구간까지의 난해성이 어떤 하한 기법과 접속 가능한가」를 체계적으로 규명하자는 아이디어다.
- 희소집합 붕괴 판정 경로
Berman–Hartmanis 동형 추측과, Mahaney 정리 같은 희소집합 붕괴 정리, Ladner 정리가 보인 NP 내부 차수 구조(조밀한 상반격자)를 「P=NP 라면 성립할 수 없는(혹은 반드시 성립해야 하는) 구조적 성질의 목록」으로 통합하고, 환원 유형 × 희소성·구조 수준 격자의 미해결 칸을 한 칸씩 메우자는 구조 복잡도 아이디어다.
- 정보 병목 엔트로피 경로
통신 복잡도에서 성숙한 정보 복잡도 도구를 회로 자체에 이식해, 회로의 절단을 가로지르는 정보량으로 「정보 흐름 병목」 측도를 정의하고 압축 모순으로 회로 하한을 얻는 경로를 설계하자는 아이디어다. Razborov 의 열등모듈러 측도 한계를 깨는 측도 설계가 중심 문제다.
- 부울 해석·해바라기 경로
Huang 의 감도 추측 해결과 ALWZ 의 해바라기 문턱 개선 같은 최근의 무조건적 돌파를 회로 하한의 역사적 엔진과 같은 계보로 보고, 해석적 측도들을 교환 가능한 하한 부품으로 표준화한 「도구 사전」을 만들어 AC0[⊕] 와 드모르간 식의 고정 다항 크기 구간(n^3 벽)처럼 자연 증명 장벽이 아직 문제되지 않는 약한 영역의 하한을 밀어 올리자는 아이디어다.
- 자기환원 체커 경로
SAT 의 하향 자기 환원성과 프로그램 체킹·자기 교정·산술화 같은 검증 장치를 「P=NP 세계가 반드시 만족해야 하는 구조적 제약 조건의 추출기」로 재해석하고, 대화형 증명이 NEXP/MA 수준에서 낸 무조건적 하한 전선을 NP 쪽으로 한 단계씩 끌어내리자는 아이디어다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.