論文の概要: A Circuit Complexity Formulation of Algorithmic Information Theory
- arxiv url: http://arxiv.org/abs/2306.14087v1
- Date: Sun, 25 Jun 2023 01:30:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 17:02:44.648099
- Title: A Circuit Complexity Formulation of Algorithmic Information Theory
- Title（参考訳）: アルゴリズム情報理論の回路複雑度定式化
- Authors: Cole Wyeth and Carl Sturtivant
- Abstract要約: インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
- 参考スコア（独自算出の注目度）: 1.5483078145498086
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inspired by Solomonoffs theory of inductive inference, we propose a prior
based on circuit complexity. There are several advantages to this approach.
First, it relies on a complexity measure that does not depend on the choice of
UTM. There is one universal definition for Boolean circuits involving an
universal operation such as nand with simple conversions to alternative
definitions such as and, or, and not. Second, there is no analogue of the
halting problem. The output value of a circuit can be calculated recursively by
computer in time proportional to the number of gates, while a short program may
run for a very long time. Our prior assumes that a Boolean function, or
equivalently, Boolean string of fixed length, is generated by some Bayesian
mixture of circuits. This model is appropriate for learning Boolean functions
from partial information, a problem often encountered within machine learning
as "binary classification." We argue that an inductive bias towards simple
explanations as measured by circuit complexity is appropriate for this problem.
- Abstract（参考訳）: インダクティブ推論のソロモンオフ理論に着想を得て,回路複雑性に基づく事前提案を行う。
このアプローチにはいくつかの利点がある。
まず、UTMの選択に依存しない複雑性尺度に依存する。
ブール回路の普遍的な定義は、nand のような普遍的な演算と、and や not のような別の定義への単純な変換を含む。
第二に、停止問題の類似は存在しない。
回路の出力値は、ゲート数に比例した時間でコンピュータによって再帰的に計算でき、短いプログラムは非常に長い時間実行することができる。
我々の以前の仮定では、ブール関数、またはそれと同値な長さのブール弦は、ある種のベイズ回路の混合によって生成される。
このモデルは、部分的情報からブール関数を学ぶのに適しており、機械学習内で「バイナリ分類」としてしばしば発生する問題である。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切である。
関連論文リスト
- On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Boolean Matching Reversible Circuits: Algorithm and Complexity [16.397487896227766]
入力否定と置換の同値性は量子時間では可逆であり、古典的な複雑性は指数関数的であることを示す。
この結果は、自動化問題の解決における量子指数的スピードアップの初めての実証である。
論文 参考訳（メタデータ） (2024-04-18T13:47:17Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - Circuit complexity and functionality: a thermodynamic perspective [2.2988732018837177]
与えられた機能の回路に対する複雑性と熱力学の関連について検討する。
特に、我々のフレームワークは任意の長さのプログラムの難読化に関する新しい視点を提供する。
我々は、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
論文 参考訳（メタデータ） (2023-09-11T18:02:21Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:45:48Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳（メタデータ） (2022-09-08T17:55:30Z) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
量子クエンチが量子場理論の回路複雑性に及ぼす影響について検討する。
待ち行列および相互作用場理論における回路複雑性の解析計算について述べる。
論文 参考訳（メタデータ） (2022-09-07T18:00:03Z) - Symbolic Synthesis of Clifford Circuits and Beyond [0.0]
ユニタリ性問題は一般にコ-NP-ハードであるが、クリフォードパス和に制限された場合、P であることを示す。
次に、一意的なクリフォード経路和からクリフォード回路を合成するアルゴリズムを提供する。
また、任意の経路和に対する抽出アルゴリズムの一般化も提供する。
論文 参考訳（メタデータ） (2022-04-29T16:33:42Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Learning algorithms from circuit lower bounds [0.0]
構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。
難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
論文 参考訳（メタデータ） (2020-12-28T04:47:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。