반쯤 채워진 매직 스퀘어 문제가 NP- 완전합니까? 6 _ 5 1 >>>

여기 문제가 있습니다 :

일부 셀에는 1.N의 숫자가있는 사각형이 있습니다. 마법의 광장으로 완성 할 수 있는지 결정해야합니다.

예 :

2 _ 6       2 7 6
_ 5 1  >>>  9 5 1
4 3 _       4 3 8

7 _ _
9 _ _  >>>  NO SOLUTION
8 _ _

이 문제가 NP-complete입니까? 그렇다면 어떻게 증명할 수 있습니까?

MS의 크로스 포스트

답변

부분적으로 채워진 라틴 사각형을 채우는 것은 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$
n
$n$
n

$1, 2, \dots, n^{2}$

1,2,…,n2

$n$

$n^{2}$

$x_{i} = 1$
xi=1
$x_{i} = x_{j} + x_{k}$
xi=xj+xk
$i, j, k \in {1, 2, \dots, n}$
i,j,k∈{1,2,…,n}
$x_{i}$
xi
${\sqrt{5}}^{n - 1}$
5n−1

이것은 또한 정리 4.7로 나타납니다.

Apoloniusz Tyszka, R과 C의 산술에 대한 두 가지 추측 , 수학. 로그. 쿼트. 56 175–184, 2010.

$2^{n}$

$2^{n - 1}$

2n−1

$x_{i} = 1$
xi=1
$x_{i} = x_{j} + x_{k}$
xi=xj+xk
$i, j, k \in {1, 2, \dots, n}$
i,j,k∈{1,2,…,n}
$x_{i}$
xi
$2^{n}$
2n

$2^{n - 1}$

2n−1

결과는 다음과 같습니다.

$N$
N
$2^{O (N^{2})}$
2O(N2)

$O (N^{4})$

O(N4)

$O (N^{8})$

O(N8)

$n^{2} + 2 (n + 1) (n - 2) + 1 = 3 n^{2} - 2 n - 3$

n2+2(n+1)(n−2)+1=3n2−2n−3

$n - 2$

n−2

$m$

$O (m^{2})$

O(m2)

$n$

INTEGER LINEAR PROGRAMMING 인스턴스의 솔루션에 Papadimitriou의 경계를 사용하면 숫자가 모두 음수가 아닌 버전도 NP에 있음을 알 수 있습니다.

$A$
A
$r \times s$
r×s
$b$
b
$r$
r
${- a, - a + 1, \dots, a - 1, a}$
{−a,−a+1,…,a−1,a}
$A x = b$
Ax=b
${0, 1, \dots, s (r a)^{2 r + 1}}$
{0,1,…,s(ra)2r+1}

$a = 1$

a=1

$s = n^{2} + 1$

s=n2+1

$r = 2 n + 2$

r=2n+2

Christos H. Papadimitriou, 정수 프로그래밍의 복잡성에 대한 JACM 28 765–768, 1981. ( link )

How IT

언제든지 물어보세요.

반쯤 채워진 매직 스퀘어 문제가 NP- 완전합니까? 6 _ 5 1 >>>

답변

답변

답변