論文の概要: On the Complexity of Computing G\"odel Numbers
- arxiv url: http://arxiv.org/abs/2302.04213v1
- Date: Wed, 8 Feb 2023 17:31:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 15:26:55.473197
- Title: On the Complexity of Computing G\"odel Numbers
- Title（参考訳）: G\"odel数計算の複雑さについて
- Authors: Vasco Brattka
- Abstract要約: 計算可能なすべての列の問題を研究し、Wehrauchの複雑性を分類する。
分類のベンチマークとして、閉かつコンパクトな選択問題とそれらの自然数へのジャンプを用いる。
これらの問題は、逆数学におけるカービー・パリ階層から知られているように、帰納法と有界性原理に対応している。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a computable sequence of natural numbers, it is a natural task to find
a G\"odel number of a program that generates this sequence. It is easy to see
that this problem is neither continuous nor computable. In algorithmic learning
theory this problem is well studied from several perspectives and one question
studied there is for which sequences this problem is at least learnable in the
limit. Here we study the problem on all computable sequences and we classify
the Weihrauch complexity of it. For this purpose we can, among other methods,
utilize the amalgamation technique known from learning theory. As a benchmark
for the classification we use closed and compact choice problems and their
jumps on natural numbers, and we argue that these problems correspond to
induction and boundedness principles, as they are known from the Kirby-Paris
hierarchy in reverse mathematics. We provide a topological as well as a
computability-theoretic classification, which reveal some significant
differences.
- Abstract（参考訳）: 計算可能な自然数の列が与えられたとき、この列を生成するプログラムの G\"odel number を見つけることは自然なタスクである。
この問題は連続的でも計算可能でもないことが分かりやすい。
アルゴリズム学習理論では、この問題はいくつかの観点からよく研究されており、ある質問では、この問題がどの順序でその極限において少なくとも学習可能であるかが論じられている。
ここでは、すべての計算可能な列の問題を研究し、Wehrauch複雑性を分類する。
この目的のために、学習理論で知られている融合技術を利用することができる。
分類のベンチマークとして、我々は閉かつコンパクトな選択問題とその自然数へのジャンプを使い、これらの問題は帰納的および有界性原理に対応し、それらは逆数学のカービー・パリ階層から知られている。
位相的および計算可能性理論的な分類を提供し,いくつかの重要な違いを明らかにした。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳（メタデータ） (2024-02-01T09:18:34Z) - Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。
Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。
また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
論文 参考訳（メタデータ） (2023-06-14T12:40:54Z) - Exceeding Computational Complexity Trial-and-Error Dynamic Action and
Intelligence [0.0]
計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。
本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。
また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
論文 参考訳（メタデータ） (2022-12-22T21:23:27Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - An Algebraic-Geometry Approach to Prime Factorization [0.0]
素因数分解のための新しいアルゴリズムは、暗号アルゴリズムの現在の実装に実践的な影響を与える可能性がある。
n/2以上のパラメータを効率的に評価できる多様体が存在することを示す。
ある場合、 n/2 以上のパラメータが与えられたとき、効率的に点を評価できる多様体が存在することを示す。
論文 参考訳（メタデータ） (2022-09-23T15:31:07Z) - Enumeration Classes Defined by Circuits [0.5161531917413706]
グラフ理論、グレイコード列挙、命題充足性からよく知られた列挙問題を見つける。
我々は$mathbfDelayP$で知られている様々な問題の複雑さを区別するフレームワークを得る。
論文 参考訳（メタデータ） (2022-05-01T19:02:03Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Learning Union of Integer Hypercubes with Queries (Technical Report) [0.0]
本稿では,d次元整数格子上での整数ハイパーキューブの有限和を求める問題について検討する。
非固定次元において、問題はDNF式を学習する問題を仮定する。
我々の問題には、量化子なし整数線型算術公式のモナディック分解問題への自然な応用がある。
論文 参考訳（メタデータ） (2021-05-27T11:39:10Z) - A simple geometric proof for the benefit of depth in ReLU networks [57.815699322370826]
本論文では, 多層フィードフォワードネットワークにおける深度の利点を, 整流活性化(深度分離)により証明する。
我々は、線形深さ($m$)と小さな定数幅($leq 4$)を持つ具体的なニューラルネットワークを示し、問題をゼロエラーで分類する。
論文 参考訳（メタデータ） (2021-01-18T15:40:27Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。