論文の概要: How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

• arxiv url: http://arxiv.org/abs/2604.26972v1
• Date: Fri, 24 Apr 2026 14:23:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-01 16:31:53.684041
• Title: How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
• Title（参考訳）: 連続的なクラスタリングはどれくらい難しいか? 実数理論から見る境界
• Authors: Angshul Majumdar,
• Abstract要約: 本稿では,確率密度に基づいて直接定義されるクラスタリング問題の計算困難さについて検討する。 まず、互いに遠く離れた高密度の点がいくつか存在するか。 第二に、2つの高密度点が低密度の中間点を持ち、その中間点の間に谷が形成される。 第三に、密度がしきい値を超える領域は、少なくとも与えられた数の連結部分を持つ。 第4に、同じ領域には穴があり、つまり一点まで縮小できないループがある。
• 参考スコア（独自算出の注目度）: 11.62669179647184
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the computational difficulty of clustering problems that are defined directly on a continuous probability density. Rather than working with finite samples, we assume the density is given as a polynomial and ask whether it contains certain cluster structures. Four natural questions are examined. First, do there exist several points with high density that are far apart from each other. Second, do two high density points have a midpoint with low density, creating a valley between them. Third, does the region where the density is above a threshold have at least a given number of separate connected pieces. Fourth, does that same region contain a hole, meaning a loop that cannot be shrunk to a point. We prove that the first two problems, separated points and valley detection, are exactly as hard as the existential theory of the reals, a complexity class that contains NP and is believed to be strictly larger. In contrast, the topological problems of counting connected pieces and detecting holes are at least as hard as the existential theory of the reals, but their exact complexity remains open. Placing them inside that class would need a major advance in real algebraic geometry. These results give the first rigorous classification of exact continuous clustering inside the real polynomial hierarchy. They also show that even basic clustering criteria are not NP complete unless unexpected collapses occur.
• Abstract（参考訳）: 本稿では,連続確率密度に基づいて直接定義されるクラスタリング問題の計算困難性について検討する。 有限サンプルを扱うのではなく、密度が多項式として与えられると仮定し、あるクラスタ構造を含むかどうかを問う。 4つの自然問題が検討されている。 まず、互いに遠く離れた高密度の点がいくつか存在するか。 第二に、2つの高密度点が低密度の中間点を持ち、その中間点の間に谷が形成される。 第三に、密度がしきい値を超える領域は、少なくとも与えられた数の連結部分を持つ。 第4に、同じ領域には穴があり、つまり一点まで縮小できないループがある。 分離点と谷検出という最初の2つの問題は、NPを含む複雑性クラスである実数の存在理論と全く同じほど難しいことを証明している。 対照的に、連結部分の数え上げと検出孔の位相問題は、少なくとも実数の存在論と同じくらい難しいが、その正確な複雑性は未解決のままである。 それらのクラスをクラス内に配置するには、実際の代数幾何学において大きな進歩が必要である。 これらの結果は、実多項式階層内の正確な連続クラスタリングの最初の厳密な分類を与える。 また、予想外の崩壊が起きない限り、基本的なクラスタリング基準でさえNP完全ではないことも示している。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Bosonic Quantum Computational Complexity [1.7499351967216341]
  私たちはそのような研究計画の基礎をつくった。 本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。 ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-05T19:43:41Z)
• SDC-HSDD-NDSA: Structure Detecting Cluster by Hierarchical Secondary Directed Differential with Normalized Density and Self-Adaption [0.0]
  密度ベースのクラスタリングは最も人気のあるクラスタリングアルゴリズムである。 低密度領域で分離される限り、任意の形状のクラスターを識別することができる。 しかし、低密度領域で分離されていない高密度領域は、複数のクラスタに属する異なる構造を持つ可能性がある。 本稿では,この問題に対処する新しい密度クラスタリング手法を提案する。
  論文  参考訳（メタデータ） (2023-07-02T22:30:08Z)
• A bulk manifestation of Krylov complexity [0.0]
  我々は、Krylov や K-complexity というような複雑性のクラスに対する AdS/CFT 辞書のエントリを確立する。 我々は、AdS$の境界上の無限温度ヒルベルト熱場二重状態のクリロフ複雑性が、JT重力の正確なバルク記述を持つことを示した。 この結果はコードダイアグラム手法を広く利用し、境界量子系のクリロフ基底を同定する。
  論文  参考訳（メタデータ） (2023-05-07T18:58:26Z)
• Unextendibility, uncompletability, and many-copy indistinguishable ensembles [49.1574468325115]
  任意の二分的純絡み合った状態の補集合は、最大濃度の非直交的拡張不可能な積基底(nUPB)を形成する積状態によって分散されることを示す。 また,混合状態の減少に伴い局所的不識別性が増大する多部構成多部構成不識別アンサンブルのクラスについても報告する。
  論文  参考訳（メタデータ） (2023-03-30T16:16:41Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Hierarchical nucleation in deep neural networks [67.85373725288136]
  我々は,いくつかの最先端DCNにおいて,隠れた層にまたがるImageNetデータセットの確率密度の進化について検討した。 初期層は, 分類に無関係な構造を排除し, 一様確率密度を生成する。 その後の層では、密度ピークは階層的な方法で発生し、概念のセマンティック階層を反映する。
  論文  参考訳（メタデータ） (2020-07-07T14:42:18Z)
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? [108.94173231481355]
  長い地平線を計画する学習は、エピソード強化学習問題における中心的な課題である。 長地平線RLは、少なくともミニマックス感覚において、短地平線RLよりも困難ではないことを示す。
  論文  参考訳（メタデータ） (2020-05-01T17:56:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。