論文の概要: Finding hardness reductions automatically using SAT solvers

• arxiv url: http://arxiv.org/abs/2402.06397v1
• Date: Fri, 9 Feb 2024 13:29:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-12 16:53:03.761383
• Title: Finding hardness reductions automatically using SAT solvers
• Title（参考訳）: SATソルバを用いた自動硬さ低減
• Authors: Helena Bergold, Manfred Scheucher, Felix Schr\"oder
• Abstract要約: 完全構造に部分構造を完備化できるかどうかという決定問題は、多くの構造に対してNP完全であることを示す。 文献のほとんどを減らすためのガジェットは手作業で見つかるが、我々は完全に自動化された方法でガジェットを構築するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this article, we show that the completion problem, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many combinatorial structures. While the gadgets for most reductions in literature are found by hand, we present an algorithm to construct gadgets in a fully automated way. Using our framework which is based on SAT, we present the first thorough study of the completion problem on sign mappings with forbidden substructures by classifying thousands of structures for which the completion problem is NP-complete. Our list in particular includes interior triple systems, which were introduced by Knuth towards an axiomatization of planar point configurations. Last but not least, we give an infinite family of structures generalizing interior triple system to higher dimensions for which the completion problem is NP-complete.
• Abstract（参考訳）: 本稿では, 完全構造に部分構造を完備化できるかという決定問題である完備化問題は, 多くの組合せ構造に対してNP完全であることを示す。 文献のほとんどを減らすためのガジェットは手作業で見つかるが、我々は完全に自動化された方法でガジェットを構築するアルゴリズムを提案する。 SATをベースとした我々のフレームワークを用いて,完成問題がNP完全である何千もの構造を分類することにより,禁止部分構造を持つ手話写像の完備化問題を初めて徹底的に研究する。 特にこのリストは、knuthによって平面点構成の公理化に向けて導入された内部三重系を含む。 最後に、なおかつ重要なことは、完備問題がNP完全である高次元に内三重系を一般化する無限の構造の族を与える。

関連論文リスト

• Self-supervised Shape Completion via Involution and Implicit Correspondences [89.18705005095359]
  3次元形状の完成は、教師付きトレーニングや、完全な形状の例による分布学習によって伝統的に解決される。 近年, 完全な3次元形状の例を必要としない自己指導型学習手法が注目されている。 形状完遂作業のための非対角的自己教師型手法を提案する。
  論文  参考訳（メタデータ） (2024-09-24T10:04:38Z)
• A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2) [5.228711636020665]
  探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ複雑さを持つことを示す。 提案アルゴリズムは、3つの標準英語ベンチマークの大部分をカバーし、同等の実験結果を提供する。
  論文  参考訳（メタデータ） (2022-10-10T14:47:36Z)
• Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts [88.94020638263467]
  ブランチ・アンド・カット(ブランチ・アンド・カット)として知られる分岐・アンド・バウンドアルゴリズムにおける切断平面の組み入れは、現代の整数計画解法のバックボーンを形成する。 入力整数プログラムに付加される切断平面を定義するパラメータの変化により、アルゴリズムの各ステップがどのように影響を受けるかをピン留めする、分岐切断の新たな構造解析を行う。 この分析の主な応用は、機械学習を用いてブランチ・アンド・カット時にどの切断面を適用するかを決定するためのサンプルの複雑性保証を導出することである。
  論文  参考訳（メタデータ） (2022-04-15T03:32:40Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  本稿では、NP-hard Maximum Independent Set問題に対するオープンソースのベンチマークスイートについて、その重み付けと非重み付けの両変種について述べる。 また,Li らによる木探索アルゴリズム (NeurIPS 2018) の詳細な解析を行い,小型および大規模合成および実世界のグラフ上で様々な構成を検証した。 木探索で用いられるグラフ畳み込みネットワークは,解構造の有意な表現を学ばず,実際にランダムな値に置き換えることができることを示す。
  論文  参考訳（メタデータ） (2022-01-25T17:37:34Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Fold2Seq: A Joint Sequence(1D)-Fold(3D) Embedding-based Generative Model for Protein Design [70.27706384570723]
  Fold2Seqは特定の標的に条件付きタンパク質配列を設計するための新しいフレームワークである。 Fold2Seqの性能は, シーケンス設計の速度, カバレッジ, 信頼性において向上したか, 同等であったかを示す。 フォールドベースのFold2Seqの独特な利点は、構造ベースのディープモデルやRosettaDesignと比較して、3つの現実世界の課題においてより明確になる。
  論文  参考訳（メタデータ） (2021-06-24T14:34:24Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• 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)
• Introducing Structure to Expedite Quantum Search [0.0]
  本稿では,非構造化探索問題を1つの有意な要素で解くための新しい量子アルゴリズムを提案する。 我々のアルゴリズムは乗算定数までの基本ゲートの総数で最適である。 本稿では,複数要素を持つ非構造化探索問題の解法に必要な基本ゲートの数をトータルに削減する方法を示す。
  論文  参考訳（メタデータ） (2020-06-10T13:29:47Z)
• Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3) [5.228711636020665]
  本研究では,ブロック次数2の不連続な構成木をスパンベースで解析する新しいアルゴリズムを提案する。 より小さな検索空間と、$mathcal O(n6)$ down から $mathcal O(n3)$ までの時間複雑度を持つ変種を構築できることを示します。
  論文  参考訳（メタデータ） (2020-03-30T19:54:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。