論文の概要: Computational Short Cuts in Infinite Domain Constraint Satisfaction
- arxiv url: http://arxiv.org/abs/2211.10144v1
- Date: Fri, 18 Nov 2022 10:37:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-21 15:36:48.727783
- Title: Computational Short Cuts in Infinite Domain Constraint Satisfaction
- Title（参考訳）: 無限領域制約満足度における計算ショートカット
- Authors: Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
- Abstract要約: 有限ドメインのCSPインスタンスのバックドアは変数の集合であり、各インスタンス化がインスタンスを解決可能な時間クラスに移動させる。
このような無限領域のバックドアは、有限領域のバックドアが持つ多くの正の計算特性を持つことを示す。
バックドアの代替としてサイドドアを導入します。
- 参考スコア（独自算出の注目度）: 34.522661052004324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A backdoor in a finite-domain CSP instance is a set of variables where each
possible instantiation moves the instance into a polynomial-time solvable
class. Backdoors have found many applications in artificial intelligence and
elsewhere, and the algorithmic problem of finding such backdoors has
consequently been intensively studied. Sioutis and Janhunen (Proc. 42nd German
Conference on AI (KI-2019)) have proposed a generalised backdoor concept
suitable for infinite-domain CSP instances over binary constraints. We
generalise their concept into a large class of CSPs that allow for higher-arity
constraints. We show that this kind of infinite-domain backdoors have many of
the positive computational properties that finite-domain backdoors have: the
associated computational problems are fixed-parameter tractable whenever the
underlying constraint language is finite. On the other hand, we show that
infinite languages make the problems considerably harder: the general backdoor
detection problem is W[2]-hard and fixed-parameter tractability is ruled out
under standard complexity-theoretic assumptions. We demonstrate that backdoors
may have suboptimal behaviour on binary constraints -- this is detrimental from
an AI perspective where binary constraints are predominant in, for instance,
spatiotemporal applications. In response to this, we introduce sidedoors as an
alternative to backdoors. The fundamental computational problems for sidedoors
remain fixed-parameter tractable for finite constraint language (possibly also
containing non-binary relations). Moreover, the sidedoor approach has appealing
computational properties that sometimes leads to faster algorithms than the
backdoor approach.
- Abstract（参考訳）: 有限領域 CSP インスタンスのバックドアは変数の集合であり、各インスタンスが多項式時間解決可能なクラスにインスタンスを移動させる。
バックドアは人工知能やその他の分野で多くの応用が発見されており、そのようなバックドアを見つけるアルゴリズムの問題が研究されている。
シウティス(Sioutis)とヤンフン(Janhunen)。
42nd German Conference on AI (KI-2019) は、無限ドメインCSPインスタンスに適した一般化されたバックドアの概念を提案した。
我々はそれらの概念を高アリティ制約を許容するCSPの大規模なクラスに一般化する。
このような無限領域バックドアは、有限領域バックドアが持つ正の計算特性の多くを持っていることが示されている。
一般的なバックドア検出問題は w[2]-hard であり、固定パラメータの扱いやすさは標準的な複雑性理論の仮定では除外される。
我々は、バックドアがバイナリ制約に対して最適でない振る舞いを持つ可能性があることを実証する -- これは、例えば時空間的アプリケーションにおいてバイナリ制約が優勢であるaiの観点から有害である。
これに対し、バックドアの代替としてサイドドアを導入する。
サイドドアの基本的な計算問題は、有限制約言語(多分非バイナリ関係を含む)に対して固定パラメータの扱いが可能だ。
さらに、サイドドアアプローチは、バックドアアプローチよりも高速なアルゴリズムにつながる計算特性をアピールしている。
関連論文リスト
- Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。
インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。
多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
論文 参考訳（メタデータ） (2024-09-04T14:26:58Z) - Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。
これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。
我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文 参考訳（メタデータ） (2022-10-12T03:01:00Z) - Practical computational advantage from the quantum switch on a
generalized family of promise problems [0.0]
量子スイッチ (quantum switch) は、順序の重畳に演算を適用することで計算上の利点を提供する量子計算プリミティブである。
本研究では、より一般的な公約問題を導入するために複素アダマール行列を用いる。
論文 参考訳（メタデータ） (2022-07-26T15:57:12Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Constructive Post-Quantum Reductions [18.527533843982905]
古典的還元の大規模クラスをポストクォータム設定に変換するための正および負の結果を示す。
計算問題に対するステートフルな解法との還元(あるいは一般相互作用)のための枠組みを考案した。
論文 参考訳（メタデータ） (2022-03-04T13:46:34Z) - Finding Backdoors to Integer Programs: A Monte Carlo Tree Search
Framework [22.824450460839245]
バックドアは、以下のプロパティを持つインスタンスの整数変数の小さなサブセットである。
MIPのバックドアを見つけるためのモンテカルロ木探索フレームワークBaMCTSを提案する。
論文 参考訳（メタデータ） (2021-10-16T00:36:53Z) - Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
性能を損なわずに2次から線形に複雑性を低減できる新しい高速非局所ブロックを定式化する。
The proposed method, we dub that "Poly-NL" is competitive to state-of-the-art performance across image recognition, instance segmentation, and face detection task。
論文 参考訳（メタデータ） (2021-07-06T19:51:37Z) - Reassessing the computational advantage of quantum-controlled ordering
of gates [0.0]
量子計算において、不確定因果構造は、2つのユニタリゲートが各ゲートへの1つの呼び出しで通勤するか反通勤するかを決定する。
本研究では,この利点が期待よりも小さいことを示す。
我々は、$O(nlog(n))$クエリで唯一知られている特定のFPPを解決する因果アルゴリズムと、$O(nsqrtn)$クエリですべてのFPPを解決する因果アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-22T19:00:08Z) - Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。
本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
論文 参考訳（メタデータ） (2020-12-31T12:40:52Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。