論文の概要: CSPs with Few Alien Constraints
- arxiv url: http://arxiv.org/abs/2408.12909v1
- Date: Fri, 23 Aug 2024 08:34:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-26 15:40:04.909745
- Title: CSPs with Few Alien Constraints
- Title（参考訳）: 外国人制約の少ないCSP
- Authors: Peter Jonsson, Victor Lagerkvist, George Osipov,
- Abstract要約: CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。
我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
- 参考スコア（独自算出の注目度）: 12.330326247154968
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The constraint satisfaction problem asks to decide if a set of constraints over a relational structure $\mathcal{A}$ is satisfiable (CSP$(\mathcal{A})$). We consider CSP$(\mathcal{A} \cup \mathcal{B})$ where $\mathcal{A}$ is a structure and $\mathcal{B}$ is an alien structure, and analyse its (parameterized) complexity when at most $k$ alien constraints are allowed. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts. Our novel approach, utilizing logical and algebraic methods, yields an FPT versus pNP dichotomy for arbitrary finite structures and sharper dichotomies for Boolean structures and first-order reducts of $(\mathbb{N},=)$ (equality CSPs), together with many partial results for general $\omega$-categorical structures.
- Abstract（参考訳）: 制約満足度問題は、関係構造上の制約の集合$\mathcal{A}$が満足できるかどうかを決定するよう要求する(CSP$(\mathcal{A})$)。
CSP$(\mathcal{A} \cup \mathcal{B})$ ここで、$\mathcal{A}$は構造であり、$\mathcal{B}$はエイリアン構造であり、少なくとも$k$の制約が許されるとき、その(パラメータ化された)複雑さを分析する。
我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
論理的および代数的手法を利用して、任意の有限構造に対するFPT対pNP二分法とブール構造に対するよりシャープな二分法、および(等式CSP)$(\mathbb{N},=)$(等式CSP)の1次レダクト、および一般の$\omega$-カテゴリ構造に対する多くの部分的な結果を得る。
関連論文リスト
- A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Merging Ontologies Algebraically [1.6404357211482503]
例えば、(I)、(C)、(A)、(R)でラベル付けされた、イデペンデンス、快適性、表現性などである。
また、$V$-アライメントによって与えられるマージシステムは、(I)、(C)、(A)、(R)という特性を満たすことを示す。
論文 参考訳（メタデータ） (2022-08-18T08:57:58Z) - A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs [4.023424709659175]
制約あたり$k$変数(k-CSP)によるランダム制約満足度問題の強い反響を証明する。
割当数$p$の制約で満たされたランダムk-CSPインスタンスの場合、最適値が最大値$p+O_k(epsilon)$の制約で満足する証明書を効率的に計算できる。
論文 参考訳（メタデータ） (2022-04-20T16:21:21Z) - Local approximation of operators [0.0]
距離空間 $mathfrakX$ と $mathfrakY$ の間の非線形作用素の近似の度合いを決定する問題について検討する。
例えば、$mathbbSd$ の近似に関係する定数は $mathcalO(d1/6)$ である。
論文 参考訳（メタデータ） (2022-02-13T19:28:34Z) - On Classifying Continuous Constraint Satisfaction Problems [1.2277343096128712]
連続制約満足度問題 (CCSP) は制約満足度問題 (CSP) である。
我々は実数の実在論、すなわちER完全を完備とするCCSPを分類する。
そのような CCSP のクラス上では、曲線等式制約 (f(x,y) geq 0$ および $g(x,y) geq 0$) が ER 完全であることを示す。
論文 参考訳（メタデータ） (2021-06-04T10:23:48Z) - On the state space structure of tripartite quantum systems [0.22741525908374005]
例えば$mathcalBint(ABC)$] は3つの二分節をまたいだ正の部分的転置(PPT)を持つ状態の集合の厳密な部分集合である[$mathcalPint(ABC)$] 。
この主張は、$mathPint(ABC)$に属するが$mathcalBint(ABC)$に属さない状態を構築することで証明される。
論文 参考訳（メタデータ） (2021-04-14T16:06:58Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。
学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-16T16:12:10Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。