抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
F_pがプライム次数p≧5の有限場である,証明システムRes(lin_F_p)におけるdag様証明のサイズに対する下限を証明する新しい方法を提案した。証明システムRes(lin_F)における任意のdag-like refutionのサイズに関する指数関数的下限は,以前に,Fが特性0の分野である(Part,Tzameret,ITCS’20)で,それはCNFではなく,2値原理x_1+2x_2+s+2 ̄n-1x_n=-1であった。この下限の証明は,特性0レジームの特異性を実質的に利用し,有限場でもCNFに対しても,下限をいかに証明するかに関する手がかりを与えない。二値値原理とCNF下限の間のブリッジの構築を目的として,Aが線形マップであるb otin A({0,1} ̄n)のタウトロジーに対するdag-like Res(lin_F_p)下限を証明する方法の開発を開始した。そのようなタウロジーの否定は,Boolean割当てで不満足である線形方程式A.x=bのシステムとして,Res(lin_F_p)の言語で表現できる。この形式のインスタンスは,CNFより単純であり,これは,それらのRes(lin_F_p)の解析を,より接近可能にし,線形代数と付加結合器からのツールにより支援できる。誤り訂正符号の概念を用いて,A.x=b形式のインスタンスに対する硬度基準を同定し,著者らが導入した線形系A.x=bのコンビナトリアル,代数的特性と呼ぶ。Res(lin_F_p)の2つの相補的側面を捕獲し,一般的なdag様Res(lin_F_p)の中中に近づくためのコンビナトリアルツールボックスを構成するRes(lin_F_p)のフラグメントに対する2つの下限を証明した。【JST・京大機械翻訳】