論文の概要: Covering Polygons is Even Harder

• arxiv url: http://arxiv.org/abs/2106.02335v1
• Date: Fri, 4 Jun 2021 08:29:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-08 01:11:55.561969
• Title: Covering Polygons is Even Harder
• Title（参考訳）: ポリゴンのカバーはもっと難しい
• Authors: Mikkel Abrahamsen
• Abstract要約: MCCはMINIMUM CONVEX COVER問題において$mathsfNP$-hardであることが知られている。 MCC が $existmathbbR$-hard であることを証明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon $\mathcal P$ and an integer $k$, and the question is if there exist $k$ convex polygons whose union is $\mathcal P$. It is known that MCC is $\mathsf{NP}$-hard [Culberson & Reckhow: Covering polygons is hard, FOCS 1988/Journal of Algorithms 1994] and in $\exists\mathbb{R}$ [O'Rourke: The complexity of computing minimum convex covers for polygons, Allerton 1982]. We prove that MCC is $\exists\mathbb{R}$-hard, and the problem is thus $\exists\mathbb{R}$-complete. In other words, the problem is equivalent to deciding whether a system of polynomial equations and inequalities with integer coefficients has a real solution. If a cover for our constructed polygon exists, then so does a cover consisting entirely of triangles. As a byproduct, we therefore also establish that it is $\exists\mathbb{R}$-complete to decide whether $k$ triangles cover a given polygon. The issue that it was not known if finding a minimum cover is in $\mathsf{NP}$ has repeatedly been raised in the literature, and it was mentioned as a "long-standing open question" already in 2001 [Eidenbenz & Widmayer: An approximation algorithm for minimum convex cover with logarithmic performance guarantee, ESA 2001/SIAM Journal on Computing 2003]. We prove that assuming the widespread belief that $\mathsf{NP}\neq\exists\mathbb{R}$, the problem is not in $\mathsf{NP}$. An implication of the result is that many natural approaches to finding small covers are bound to give suboptimal solutions in some cases, since irrational coordinates of arbitrarily high algebraic degree can be needed for the corners of the pieces in an optimal solution.
• Abstract（参考訳）: 最小凸被覆 (minimum convex cover, mcc) 問題では、単純多角形 $\mathcal p$ と整数 $k$ が与えられ、問題は、結合が $\mathcal p$ であるような $k$ 凸多角形が存在するかどうかである。 mcc は $\mathsf{np}$-hard [culberson & reckhow: covering polygons is hard, focs 1988/journal of algorithms 1994] and in $\exists\mathbb{r}$ [o'rourke: the complexity of computing minimum convex covers for polygons, allerton 1982] であることが知られている。 MCC が $\exists\mathbb{R}$-hard であることを証明するので、問題は $\exists\mathbb{R}$-complete である。 言い換えると、問題は多項式方程式の系と整数係数の不等式が実解を持つかどうかを決定することと等価である。 構成した多角形に対する被覆が存在するならば、三角形からなる被覆もそうである。 したがって、副生成物として、$k$三角形が与えられたポリゴンを被覆するかどうかを決定するのに$\exists\mathbb{R}$-完全であることも証明する。 最小被覆が$\mathsf{np}$ であるかどうかが分かっていない問題は、文献で繰り返し取り上げられており、2001年に既に「長年の疑問」として言及されている(eidenbenz & widmayer: an approximation algorithm for minimum convex cover with logarithmic performance guarantee, esa 2001/siam journal on computing 2003)。 広く信じられている$\mathsf{NP}\neq\exists\mathbb{R}$と仮定すると、問題は$\mathsf{NP}$にはない。 結果として、小さな被覆を見つけるための多くの自然なアプローチは、任意の高代数次数の不合理座標が最適解の片隅に必要であるため、いくつかの場合において最適解を与えるために有界である。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
  この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
  論文  参考訳（メタデータ） (2024-03-04T18:30:33Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。 本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
  論文  参考訳（メタデータ） (2020-04-15T06:18:41Z)

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

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