論文の概要: Sampling and Complexity of Partition Function
- arxiv url: http://arxiv.org/abs/2102.00855v1
- Date: Mon, 1 Feb 2021 14:09:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-03 03:55:37.143086
- Title: Sampling and Complexity of Partition Function
- Title（参考訳）: 分割関数のサンプリングと複雑性
- Authors: Chuyu Xiong
- Abstract要約: 本稿では,パーティション関数の設定,パーティション関数の特性,使用するツールについて論じる。
このアプローチにより,分割関数の計算複雑性の下位境界と数分割問題の計算複雑性の下位境界が問題の大きさに指数関数的であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: The number partition problem is a well-known problem, which is one of 21
Karp's NP-complete problems \cite{karp}. Partition function is a boolean
function that is equivalent to the number partition problem with number range
restricted. To understand the computational complexity of the number partition
problem and partition function is quite important and hard. People speculate
that we need new tools and methods \cite{aaronson} for such problem. In our
recent research on universal learning machine \cite{paper5, paper8}, we
developed some tools, namely, fitting extremum, proper sampling set, boolean
function with parameters (used in trial-and-error fashion). We found that these
tools could be applied to the partition function. In this article, we discuss
the set up of the partition function, properties of the partition function, and
the tools to be used. This approach leads us to prove that the lower bound of
the computational complexity of partition function, as well as the lower bound
of the computational complexity of the number partition problem, is exponential
to the size of problem. This implies: {\bf P} $\ne$ {\bf NP} \cite{cook}.
- Abstract（参考訳）: 数分割問題はよく知られた問題であり、21 Karp のNP完全問題 \cite{karp} の1つである。
分割関数は、数範囲が制限された数分割問題と等価なブール関数である。
数値分割問題と分割関数の計算複雑性を理解することは極めて重要かつ困難である。
このような問題には、新しいツールとメソッド \cite{aaronson} が必要だと推測される。
汎用学習マシン \cite{paper5, paper8} に関する最近の研究で、我々は極端に適合するツール、適切なサンプリングセット、パラメータ付きブール関数(試行錯誤方式で使用される)を開発した。
これらのツールがパーティション関数に適用できることが分かりました。
本稿では,パーティション関数のセットアップ,パーティション関数のプロパティ,使用するツールについて論じる。
このアプローチは、分割関数の計算複雑性の低い境界と、数分割問題の計算複雑性の低い境界が問題の大きさに指数関数的であることを証明します。
これは次のように意味する: {\bf P} $\ne$ {\bf NP} \cite{cook}。
関連論文リスト
- A simple lower bound for the complexity of estimating partition functions on a quantum computer [0.20718016474717196]
分割関数 $mathsfZ(beta)=sum_xinchi e-beta H(x)$ をハミルトニアン$H(x)$ で特徴づけられるギブス分布に対して推定する複雑性について検討する。
我々は、ギブス状態のコヒーレントな符号化を通して反射に依存することにより、この問題を解く量子アルゴリズムの単純で自然な下界を提供する。
論文 参考訳（メタデータ） (2024-04-03T02:38:49Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - The cluster structure function [1.1168121941015012]
クラスタ構造関数は、パーティションの部品数を、その部品による良いモデルであることの欠陥に関連する値にマッピングする。
最適なクラスタリングは、クラスタ構造関数を最小限にするために選ばれたものである。
実データを用いた例を挙げる: MNIST手書き桁と、幹細胞研究で用いられる実細胞のセグメント化である。
論文 参考訳（メタデータ） (2022-01-04T16:05:59Z) - A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality
Partition Optimization [0.0]
等濃度集合分割問題の最適化版(等値分割の和の絶対差を最小化する)について検討する。
我々のアプローチでは正あるいは整数の入力は必要とせず、任意の入力精度で同じように機能する。
論文 参考訳（メタデータ） (2021-09-16T11:25:18Z) - Efficient Locally Optimal Number Set Partitioning for Scheduling,
Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。
我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文 参考訳（メタデータ） (2021-09-10T11:53:34Z) - Size and Depth Separation in Approximating Natural Functions with Neural
Networks [52.73592689730044]
本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。
我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。
また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
論文 参考訳（メタデータ） (2021-01-30T21:30:11Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
論文 参考訳（メタデータ） (2020-09-11T17:31:39Z) - The Complexity of Adversarially Robust Proper Learning of Halfspaces
with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。
この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文 参考訳（メタデータ） (2020-07-30T04:18:51Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。