論文の概要: The $n$-queens completion problem

• arxiv url: http://arxiv.org/abs/2111.11402v1
• Date: Mon, 22 Nov 2021 18:23:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-23 17:21:01.057603
• Title: The $n$-queens completion problem
• Title（参考訳）: $n$-queens 完了問題
• Authors: Stefan Glock, David Munh\'a Correia and Benny Sudakov
• Abstract要約: $n$-queens設定は、ntimes n$ チェスボード上に、互いに非攻撃的なクイーンの配置である。 1850年にナックが導入した$n$-queensの完備化問題は、与えられた部分構成を完備化できるかどうかを決定することである。
• 参考スコア（独自算出の注目度）: 1.0312968200748116
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: An $n$-queens configuration is a placement of $n$ mutually non-attacking queens on an $n\times n$ chessboard. The $n$-queens completion problem, introduced by Nauck in 1850, is to decide whether a given partial configuration can be completed to an $n$-queens configuration. In this paper, we study an extremal aspect of this question, namely: how small must a partial configuration be so that a completion is always possible? We show that any placement of at most $n/60$ mutually non-attacking queens can be completed. We also provide partial configurations of roughly $n/4$ queens that cannot be completed, and formulate a number of interesting problems. Our proofs connect the queens problem to rainbow matchings in bipartite graphs and use probabilistic arguments together with linear programming duality.
• Abstract（参考訳）: $n$-queens設定は、$n\times n$チェスボード上の互いに非攻撃的なクイーンの配置である。 1850年にネイクが導入した$n$-queensの完結問題は、ある部分構成が$n$-queens構成に完結できるかどうかを決定することである。 本稿では,この疑問の極端的側面,すなわち,完備化が常に可能となるような部分構成がどの程度小さくあるべきかについて検討する。 我々は、少なくとも$n/60$の非攻撃的な女王の配置を完了できることを示す。 また、完成できない約$n/4$のクイーンの部分構成を提供し、多くの興味深い問題を定式化します。 我々の証明はクイーンズ問題と二部グラフのレインボーマッチングを結び、線形計画双対性とともに確率的引数を用いる。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Parity vs. AC0 with simple quantum preprocessing [0.0]
  我々は、$mathsfAC0$が$mathsfQNC0$回路の測定結果に作用するハイブリッド回路モデルについて検討する。 私たちは、$mathsfQNC0$が、タスクの検索とサンプリングに驚くほど強力なのに対して、その出力のグローバルな相関において、そのパワーは"ロックアウト"されていることに気付きました。
  論文  参考訳（メタデータ） (2023-11-22T20:27:05Z)
• Higher rank antipodality [0.0]
  一般確率論に動機づけられて、集合 $X$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。 k=1$ の場合、Klee が導入した(ペアワイズで)反ポッド性の概念と一致する。
  論文  参考訳（メタデータ） (2023-07-31T17:15:46Z)
• Matching upper bounds on symmetric predicates in quantum communication complexity [0.0]
  共役共役が許されるとき、f circ G = f(G)mathrmQCC_mathrmE(G)) という形の関数の量子通信複雑性に焦点を当てる。 我々は,同じ文が共用絡み合いを持たないことを示し,その結果を一般化する。
  論文  参考訳（メタデータ） (2023-01-01T08:30:35Z)
• The Complexity of NISQ [15.842125145638693]
  NISQデバイスは、その計算能力を理解するために必須である。 本稿では、複雑性クラス $textsfNISQ $ を定義し、研究する。 3つのよく研究された問題に対して$textsfNISQ$のパワーを考慮する。
  論文  参考訳（メタデータ） (2022-10-13T17:58:32Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• The geometry of Bloch space in the context of quantum random access codes [0.0]
  QRAC(Quantum Random Access Code)と呼ばれる通信プロトコルについて検討する。 共有ランダム性を持つ任意の$(n,m,p)$-QRACに対して、$p$ は $ tfrac12+tfrac12sqrttfrac2m-1n$ で上限となる。
  論文  参考訳（メタデータ） (2021-06-01T00:15:33Z)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。 一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
  論文  参考訳（メタデータ） (2020-12-16T17:58:45Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

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

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