A Note on P $\neq$ NP

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.덧셈 mod 2^n과 비트 XNOR 중 선택해 최종값을 0으로 만드는 'Add/XNOR' 문제의 NP-완전성을 증명
2.이진 SUBSET-SUM 환원으로, 지수시간가설(ETH) 하에서 2^o(n) 시간 알고리즘 배제
3.중간에서 만나기 방식으로 O*(2^((n-1)/2)) 시간·공간의 정확한 알고리즘 구성
4.워드 너비가 피연산자 수의 고정 유리수 거듭제곱일 때도 NP-완전성 유지 확인

왜 중요한가?

제목은 P≠NP를 언급하지만 실제로는 P vs NP 미해결 문제를 증명한 것이 아니라 특정 산술·비트연산 결합 문제의 NP-완전성과 지수시간 하한을 다룬 것으로, 하한 증명 기법 연구에 참고될 수 있다.

본문 미리보기

We study the Add/XNOR decision problem: given $n$ words of $n$ bits each, choose between addition modulo $2^n$ and bitwise XNOR at each position of a left-associative expression so that its final value is zero. We prove NP-completeness by a deterministic polynomial-time reduction from binary SUBSET-SUM. Independent four-bit guard fields force each successful four-operation gadget to consist entirely of additions or entirely of XNORs. Normalization by XNOR parity prevents later gadgets from repai

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기