論文の概要: 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完全性の間の構造的な違いを示していることを願っている。
関連論文リスト
- Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
論文 参考訳(メタデータ) (2024-02-01T09:18:34Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - 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) - The (Un)Scalability of Heuristic Approximators for NP-Hard Search
Problems [25.641418039598587]
A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。
このような問題の多くに対する正確な近似もNPハードであることを示す。
論文 参考訳(メタデータ) (2022-09-07T18:02:02Z) - On Theoretical Complexity and Boolean Satisfiability [0.0]
この論文は、コンピューティング理論において最も中心的な概念をいくつか導入している。
次に,Hhorn-SAT や 3-SAT などの抽出可能な変種を探索する。
最後に,3-SATから有名なNP完全グラフ問題への還元を確立する。
論文 参考訳(メタデータ) (2021-12-22T10:13:34Z) - CombOptNet: Fit the Right NP-Hard Problem by Learning Integer
Programming Constraints [20.659237363210774]
我々は、コスト項と制約の両方を学習できる層として、整数型プログラミングソルバをニューラルネットワークアーキテクチャに統合することを目指している。
結果として得られたエンドツーエンドのトレーニング可能なアーキテクチャは、生データから特徴を共同で抽出し、最先端の整数プログラミング解法で適切な(学習した)問題を解く。
論文 参考訳(メタデータ) (2021-05-05T21:52:53Z) - 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) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。