여기 문제가 있습니다 :
일부 셀에는 1.N의 숫자가있는 사각형이 있습니다. 마법의 광장으로 완성 할 수 있는지 결정해야합니다.
예 :
2 _ 6 2 7 6
_ 5 1 >>> 9 5 1
4 3 _ 4 3 8
7 _ _
9 _ _ >>> NO SOLUTION
8 _ _
이 문제가 NP-complete입니까? 그렇다면 어떻게 증명할 수 있습니까?
답변
부분적으로 채워진 라틴 사각형을 채우는 것은 NP-Complete입니다. “일부 라틴 정사각형 완성의 복잡성”Charles J. Colbourn. 이산 응용 수학, 8 권, 1 호, 1984 년 4 월 25 ~ 30 페이지 http://dx.doi.org/10.1016/0166-218X(84)90075-1
모듈 식 산술을 통해 라틴 제곱 문제를 마법의 제곱 문제로 바꿀 수 있습니까? 내 직감은 그렇다고 말하지만 나머지 뇌에는 “다시 채점해라!”
답변
이 질문에는 두 부분이 있습니다. 첫째, NP의 문제입니까, 둘째는 NP-hard입니까?
첫 번째 부분은 명백한 증거로 긍정적 인 대답을합니다. (이전 오류를 지적한 Suresh에게 감사합니다.)
다음과 같은 방법으로 질문을 결정 문제로 공식화하십시오.
n
n
n
1,2,…,n2
n
n
n
n
n
n2
xi=1xi=xj+xk
i,j,k∈{1,2,…,n}
xi
5n−1
이것은 또한 정리 4.7로 나타납니다.
- Apoloniusz Tyszka, R과 C의 산술에 대한 두 가지 추측 , 수학. 로그. 쿼트. 56 175–184, 2010.
2n
2n−1
2n−1xi=1
xi=xj+xk
i,j,k∈{1,2,…,n}
xi
2n
결과는 다음과 같습니다.
N
2O(N2)
O(N4)
O(N8)
n2+2(n+1)(n−2)+1=3n2−2n−3
n−2
m
O(m2)
n
INTEGER LINEAR PROGRAMMING 인스턴스의 솔루션에 Papadimitriou의 경계를 사용하면 숫자가 모두 음수가 아닌 버전도 NP에 있음을 알 수 있습니다.
A
r×s
b
r
{−a,−a+1,…,a−1,a}
Ax=b
{0,1,…,s(ra)2r+1}
a=1
s=n2+1
r=2n+2
- Christos H. Papadimitriou, 정수 프로그래밍의 복잡성에 대한 JACM 28 765–768, 1981. ( link )