Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard

기술적 요약: 텐서 스펙트럴 임계값 문제는 $\exists\mathbb{R}$-Hard 임

문제 공식화
본 논문은 텐서 스펙트럴 임계값 (Tensor Spectral Threshold) 문제의 계산 복잡성을 조사합니다. 실행 가능 영역 (단위 구의 곱) 의 컴팩트성으로 인해 텐서 스펙트럴 노름의 최대화자의 존재는 자명하지만, 노름의 값에 관한 결정 문제는 비자명합니다. 구체적으로, 텐서 $T$와 유리수 스칼라 $\alpha$가 주어졌을 때, 스펙트럴 노름 $\|T\|_{op}$가 $\alpha$를 초과하는지 여부를 묻는 문제입니다.

$d$차 대칭 텐서의 경우, 이는 단위 벡터 $x$에 대해 $|T(x, \dots, x)| \ge \alpha$를 만족하는 $x$가 존재하는지 결정하는 것과 동치입니다. 특히 4 차 텐서의 경우, 이는 단위 구 위에서 동차 4 차 다항식이 적어도 $\alpha$의 값을 달성하는지 여부를 결정하는 문제로 축소됩니다. 저자들은 "최적해의 달성 (attainment)"을 묻는 공식화 (최적화자가 존재하는지 묻는 것) 는 항상 YES 인스턴스이므로, 이 임계값 공식화가 올바른 복잡도 이론적 대상이라고 주장합니다.

방법론 및 축소 체인
본 논문은 순수 대수적, 다항 시간 축소 체인을 통해 텐서 스펙트럴 임계값 문제가 $\exists\mathbb{R}$-hard임을 입증합니다. 이 증명은 KKT 조건, 라그랑주 쌍대성, 또는 변분적 논증과 같은 최적화 이론적 장비를 피합니다. 대신 다항식 형태가 실행 가능성 제약 조건을 인코딩할 수 있는 구조적 능력에 의존합니다. 축소는 두 가지 주요 단계로 진행됩니다:

1. 유계 4 차 등식에서 동차 2 차 구 실행 가능성 (HQSF) 으로:

   • 출처: 축소는 유계 4 차 등식 실행 가능성 (BQ4E) 문제에서 시작합니다. 이는 4 차 다항식 $h(x)=0$이 하이퍼큐브 $[-1, 1]^n$ 내에서 해를 갖는지 묻는 문제이며, 이는 $\exists\mathbb{R}$-hard 임이 알려져 있습니다.
   • 변환: 저자들은 유계 4 차 인스턴스를 단위 구 위의 동차 2 차 방정식 시스템으로 변환합니다.
     • 동차화: 4 차 방정식을 동차 형태로 변환하기 위해 새로운 변수가 도입됩니다.
     • 박스 인코딩: 슬랙 변수를 사용하여 박스 제약 조건 $[-1, 1]^n$을 2 차 등식 ($z_i^2 + s_i^2 - x_0^2 = 0$) 으로 인코딩합니다.
     • 2 차 리프팅: 4 차 동차 다항식을 원래 변수들의 곱을 나타내는 새로운 변수들 (예: $u_{ab} = v_a v_b$) 을 도입하여 2 차 방정식 시스템으로 리프팅합니다.
   • 정규화: 시스템은 자명한 영해 (zero solution) 를 배제하기 위해 단위 구로 정규화되어 동차 2 차 구 실행 가능성 (HQSF) 인스턴스를 생성합니다.

2. HQSF 에서 텐서 스펙트럴 임계값으로:

   • 목표: HQSF 인스턴스는 대칭 행렬 집합 $\{Q_i\}$에 대해 $z^\top Q_i z = 0$을 만족하는 단위 벡터 $z$를 찾는 것입니다.
   • 구성: 저자들은 특정 동차 4 차 다항식을 구성합니다:
     $$p(z) = B\|z\|^4 - \sum_{i=1}^r (z^\top Q_i z)^2$$
     여기서 $B$는 행렬 $Q_i$의 제곱된 프로베니우스 노름의 합보다 엄격히 큰 상수입니다.
   • 동치성:
     • 2 차 시스템이 실행 가능 (즉, 모든 $z^\top Q_i z = 0$인 $z$가 존재) 하면, $p(z) = B$가 됩니다.
     • 시스템이 실행 불가능하면, 제곱합 항이 엄격히 양수가 되어 $p(z) < B$를 강제합니다.
     • $p(z)$는 구 위에서 엄격히 양수이므로, $|p(z)|$를 최대화하는 것은 $p(z)$를 최대화하는 것과 동치입니다.
   • 텐서화: 대칭 텐서와 동차 다항식 간의 대응에 따라, $p(z)$는 대칭 4 차 텐서 $T_p$로 표현됩니다. 구 위에서 $|p(z)|$의 최댓값은 정확히 스펙트럴 노름 $\|T_p\|_{sym, op}$입니다. 따라서 $\|T_p\|_{sym, op} \ge B$인지 결정하는 것은 원래 2 차 시스템의 실행 가능성을 결정하는 것과 동치입니다.

주요 기여

• 올바른 결정 공식화: 본 논문은 텐서 스펙트럴 노름에 적합한 결정 공식화로 텐서 스펙트럴 임계값 문제를 식별하여, 자명한 달성 문제와 구별합니다.
• $\exists\mathbb{R}$-Hardness 증명: 텐서의 스펙트럴 노름이 유리수 임계값을 초과하는지 결정하는 것이 $\exists\mathbb{R}$-hard 임을 증명합니다. 이는 다항식 시스템의 실수 해 존재 여부를 결정하는 복잡도 클래스에 해당하며, NP-hardness 와는 구별되며 일반적으로 더 어렵다고 여겨집니다.
• 대수적 축소: 축소는 완전히 대수적이고 명시적입니다. NP-hardness 증명에서 흔히 발견되는 조합적 장치나 이산 인코딩에 의존하지 않고, 2 차 시스템과 4 차 형태 간의 내재적 관계를 활용합니다.
• 견고성: 결과가 다음으로 확장됨이 입증되었습니다:
  • 비대칭 텐서 (대칭 텐서가 부분집합이므로).
  • 제약 조건을 보존하는 임베딩을 통한 고차 텐서 ($d \ge 4$).
  • 반의 대칭화 정리를 통한 다중선형 공식화.
  • 등식 변형 ($\|T\|_{op} = \alpha$인지 결정).

결과 및 의의
주요 결과는 텐서 스펙트럴 노름의 계산적 장애물이 단순히 비볼록 최적화나 조합적 탐색의 결과가 아니라, 근본적으로 실수 대수적 실행 가능성에 뿌리를 두고 있다는 점입니다.

• 개념적 전환: 본 논문은 텐서 문제를 반대수 기하학의 렌즈를 통해 바라보아야 한다고 주장합니다. 난이도는 4 차 형태가 자연스럽게 2 차 방정식 시스템을 인코딩할 수 있고, 대칭 텐서는 단순히 위장된 4 차 형태이기 때문에 발생합니다.
• 알고리즘에 대한 함의: 이 결과는 정확한 텐서 스펙트럴 임계값 문제에 대한 다항 시간 알고리즘이 $\exists\mathbb{R} \subseteq P$를 의미함을 시사합니다. 또한, 정확한 결정 문제가 이미 $\exists\mathbb{R}$-hard 이므로 일반 텐서 스펙트럴 문제에 대한 단순한 처리 가능성의 특징화 (characterization) 는 기대하지 말아야 함을 시사합니다.
• 이전 연구와의 관계: 이전 연구 (예: Håstad; Hillar 와 Lim) 가 텐서 랭크와 근사에 대해 NP-hardness 를 확립한 반면, 본 논문은 스펙트럴 노름 자체의 난이도에 대한 대수적 본질을 격리함으로써 이해를 정제합니다. 이는 실수 대수적 실행 가능성 수준에서 난이도를 확립함으로써 기존 이산적 난이도 결과를 보완합니다.

한계와 범위
저자들은 명시적으로 $\exists\mathbb{R}$-hardness를 확립하지만, 특정 인코딩 하에서의 $\exists\mathbb{R}$ 소속성 (membership) 을 다루지 않았으므로 $\exists\mathbb{R}$-completeness를 주장하지는 않는다고 밝힙니다. 축소는 4 차 구조 (4 차) 에 의존하며, 분석은 근사나 수치적 복잡성이 아닌 정확한 결정 문제로 제한됩니다. 본 논문은 새로운 알고리즘이나 실험적 응용을 제안하지 않고, 엄격하게 이론적 복잡도 분류에 초점을 맞춥니다.