論文の概要: When Input Integers are Given in the Unary Numeral Representation
- arxiv url: http://arxiv.org/abs/2312.04348v1
- Date: Thu, 7 Dec 2023 15:09:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 14:29:57.914223
- Title: When Input Integers are Given in the Unary Numeral Representation
- Title（参考訳）: 入力整数が一進数表現で与えられるとき
- Authors: Tomoyuki Yamakami
- Abstract要約: 多くのNP完全問題は、入力インスタンスの一部として整数を取る。
数値の「統一」は、問題の計算複雑性に著しく異なる効果をもたらすことが知られている。
入力整数を単項で表すと容易に解けるNP完全問題(NP完全問題)が多数存在する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many NP-complete problems take integers as part of their input instances.
These input integers are generally binarized, that is, provided in the form of
the "binary" numeral representation, and the lengths of such binary forms are
used as a basis unit to measure the computational complexity of the problems.
In sharp contrast, the "unarization" (or the "unary" numeral representation) of
numbers has been known to bring a remarkably different effect onto the
computational complexity of the problems. When no computational-complexity
difference is observed between binarization and unarization of instances, on
the contrary, the problems are said to be strong NP-complete. This work
attempts to spotlight an issue of how the unarization of instances affects the
computational complexity of various combinatorial problems. We present numerous
NP-complete (or even NP-hard) problems, which turn out to be easily solvable
when input integers are represented in unary. We then discuss the computational
complexities of such problems when taking unary-form integer inputs. We hope
that a list of such problems signifies the structural differences between
strong NP-completeness and non-strong NP-completeness.
- Abstract（参考訳）: 多くのNP完全問題は、入力インスタンスの一部として整数を取る。
これらの入力整数は一般に二項化され、すなわち「二項」数表現の形で与えられ、そのような二項形式の長さは問題の計算複雑性を測定する基礎単位として使用される。
対照的に、数値の「無数化(unarization)」(あるいは「無数」数字表現)は、問題の計算複雑性に著しく異なる効果をもたらすことが知られている。
インスタンスのバイナリ化とunarizationの間に計算複雑度差が観測されない場合、この問題は強いnp完全であると言われている。
この研究は、インスタンスの統一化が様々な組合せ問題の計算複雑性にどのように影響するかという問題を浮き彫りにしようとしている。
入力整数がユニタリで表される場合に容易に解くことができるnp完全問題(あるいはnpハード問題)を多数提示する。
次に,不定形整数入力を取る場合の計算の複雑さについて考察する。
このような問題の一覧は、強いNP完全性と非強いNP完全性の間の構造的な違いを示していることを願っている。
関連論文リスト
- MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
大規模言語モデル(LLM)は、高い精度で算術語問題を解くことができるが、訓練された言語よりも複雑な問題にどのように一般化するかは、ほとんど分かっていない。
本研究では、任意に複雑な算術証明問題に対する LLM の評価フレームワーク、MathGAP を提案する。
論文 参考訳（メタデータ） (2024-10-17T12:48:14Z) - 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) - Atom Cavity Encoding for NP-Complete Problems [5.482856804346147]
我々は、カープの21個のNP完全問題の大部分を含む、多数のNP完全問題に対する符号化スキームを提案する。
このような計算問題を, 原子数の線形コストで, 原子キャビティ・システムによって符号化できることが判明した。
本研究は,NP完全問題の解法において,原子空洞系の実用的な量子的優位性を求めるための重要なガイダンスを提供することを期待している。
論文 参考訳（メタデータ） (2024-07-16T15:32:42Z) - Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach [0.0]
完全拡張である引数の集合の確率を計算する複雑なタスクのアルゴリズムを開発する。
実験的評価は我々のアプローチの可能性を示唆している。
論文 参考訳（メタデータ） (2024-07-06T12:08:38Z) - Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳（メタデータ） (2024-02-01T09:18:34Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - 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) - On Theoretical Complexity and Boolean Satisfiability [0.0]
この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。
次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。
最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
論文 参考訳（メタデータ） (2021-12-22T10:13:34Z) - Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
本稿では,部分和問題として知られるNP完全決定問題のクラスに対する解を求めるGrover探索を提案する。
各問題インスタンスは、一組の量子ビットの中央スピンやボソンへのカップリングに符号化され、溶液を知らずにオラクルの実現を可能にする。
論文 参考訳（メタデータ） (2020-09-11T17:31:39Z) - Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。
ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
論文 参考訳（メタデータ） (2020-07-07T17:03:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。