유클리드 최근접벡터 문제(CVP)와 이진 최근접코드워드 문제의 근사 난이도에 관한 두 가지 결정론적 비근사성 결과를 증명한 논문이다. 첫째, CVP를 n^(1/2-ε) 이내로 근사하는 것이 NP-난해임을 보이되, 이 문제가 coNP에 속해 있어 NP=coNP가 아닌 한 이 지수를 C√n 수준으로 개선할 수 없음을 함께 논증한다. 둘째, 이진 최근접코드워드와 이진 신드롬 디코딩의 갭 버전이 결정론적 다항시간 다대일 환원 하에서 n^(1-ε) 배율로 NP-난해임을 보여, 두 최적화 문제 모두 동일 배율 내 근사가 NP-난해임을 함의한다. 이는 기존 OpenAI 보고서 7장에 제시된 n^(1/200) 난이도 배율을 크게 개선한 결과다.
- •유클리드 최근접벡터문제(CVP)의 n^(1/2-ε) 근사가 NP-난해임을 증명
- •CVP가 coNP에 속해 근사 배율을 C√n으로 개선하면 NP=coNP가 되어 불가능함을 논증
- •이진 최근접코드워드·신드롬 디코딩의 n^(1-ε) 근사도 NP-난해임을 결정론적 환원으로 증명
- •두 문제 모두 동일 배율 내 근사가 어렵다는 결론 도출
- •기존 n^(1/200) 난이도 배율(OpenAI 보고서 7장)을 대폭 개선
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Hardness of Euclidean Closest Vector within $n^{1/2-\epsilon}$ and Binary Nearest Codeword within $n^{1-\epsilon}$
- 1.유클리드 최근접벡터 문제, 모든 고정 ε에 대해 n^(1/2-ε) 근사가 NP-hard임을 증명
- 2.이 문제가 coNP에 속하면 NP=coNP가 되어 계수 개선 한계(C√n)를 논증
- 3.이진 최근접 코드워드·신드롬 디코딩도 n^(1-ε) 계수로 NP-hard 증명
- 4.기존 n^(1/200) 하드니스 계수 대비 크게 개선
왜 중요한가?
격자 기반 암호의 안전성 근거인 최근접벡터·코드워드 문제의 근사 하드니스 하한을 크게 끌어올린 이론적 결과다.
본문 미리보기
We prove two deterministic inapproximability results. First, for every fixed $00$ [AR05]. An NP-hard problem lying in $\mathrm{coNP}$ would give $\mathrm{NP}=\mathrm{coNP}$, so the factor $n^{1/2-\epsilon}$ above cannot be improved to $C\sqrt n$ unless the two classes coincide. Second, for every fixed $0<\epsilon<1$, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor $n^{1-\epsilon}$ under deterministic polynomial-time many-one reductions, wh
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
