【課題】充足可能性問題は、その対象となる式の構造により難易度が変わるが、ＳＡＴの式を正規化して効率的に構造を抽出する汎用性の高いＳＡＴ解法が存在しなかった。また、ＣＮＦをＨｏｒｎＣＮＦに効率的に変換するプログラムが存在しなかった。
【解決手段】ＣＮＦをその構造に従って解析する。ＣＮＦの共通の変数を持つ項同士の関係を正規化し、順序対やＨｏｒｎＣＮＦ、有向グラフに変換することとした。また、その順序対やＨｏｒｎＣＮＦ、有向グラフに変換したＣＮＦを使用することで効率的にＳＡＴを解くこととした。また、ＣＮＦの計算困難性の重要な点である相補部を持つ項同士の関係からＣＮＦＳＡＴの計算困難性を見積もることとした。 （もっと読む）

【課題】連立方程式^~f(x,y)=^~g(x,y)=0が可解であることを保証する許容誤差限界を下から評価する技術を提供する。
【解決手段】体Ｋ上の二変数多項式f(x,y),g(x,y)∈Ｋ[x,y]を以下のように書く。f(x,y) = a_d(y)x^d + … + a₁(y)x + a₀(y),g(x,y) = b_e(y)x^e + … + b₁(y)x + b₀(y)。ただし、a_d(y), b_e(y)は定数0ではないとする。このとき、条件１[a_d(y)とb_e(y)が共通零点を持たない]および条件２[Res_x(f,g)が定数ではない]を共に満たすならば、f(x,y)=g(x,y)=0には（複素数体上に）解が存在する。Res_x(f,g)はf(x,y)とg(x,y)のxに関する終結式である。この証明された事実を係数に誤差を含む二変数多項式^~f(x,y),^~g(x,y)に適用する。 （もっと読む）

【課題】実係数多項式ｐ（Ｘ）が実係数多項式ｆ（Ｘ）で割り切れるような実係数多項式ｐ（Ｘ），ｆ（Ｘ）がそれぞれ実区間多項式Ｐ（Ｘ），Ｆ（Ｘ）の中に存在するかどうかを判定するための技術を提供する。
【解決手段】第一実区間多項式Ｐ（Ｘ）を第二実区間多項式Ｆ（Ｘ）で割った剰余を求める。剰余の同類項をまとめた場合に上記剰余はｍ（ｍは１以上の整数）個の項から構成されるとして、上記ｍ個の項のそれぞれの係数から成るｍ個の制約多項式Ｆ（Ｃ）を生成する。区間ヤコビ行列Ｊ（ｃ^＊（ｋ），Ｃ^Ｉ（ｋ））を用いてＦ（Ｃ）＝０を線形化した後に、区間ガウスの消去法を用いて連立区間多項式Ｆ（Ｃ）＝０についての緩和した解Ｎ’（ｃ^＊（ｋ），Ｃ^Ｉ（ｋ））を求める。Ｎ（ｃ^＊（ｋ），ｑ^Ｉ（ｋ））⊆上記領域Ｃ^Ｉ（ｋ）であれば、上記第一実区間多項式が上記第二実区間多項式を擬因子として持つと判定できる。 （もっと読む）

【課題】本発明は、解く必要のある方程式の数がｅ_ｊ（ｘ）の数の多項式オーダで収まる方法を提供することを目的とする。
【解決手段】本発明の距離算出装置は、記録部、多項式判定部、第１計算部、第２計算部 を備える。第１計算部は、集合Δと集合Δ^〜と集合Ｚ^〜と集合Ｚを求めるΔ、Δ^〜、Ｚ^〜、Ｚ計算手段、集合Δ＼Ｚ^〜と集合Ｊ＼Ｚを求めるΔ＼Ｚ^〜、Ｊ＼Ｚ計算手段、φ_ｊ（σ）計算手段、Φ（σ）計算手段、実閉区間確認手段、ｍ計算手段、ｍ決定手段を有する。 （もっと読む）

【課題】実区間多項式が実係数多項式を実因子として持っているか判定する。
【解決手段】実区間多項式Σ[l_i, h_i]e_i(x)を各e_i(x)ごとに実係数多項式ｆで割り算して剰余r_i(x)を求め、l_i=h_iとなる番号があればそれらに対する剰余を足し合わせてr₀(x)とし、r_i(x)=0となるものははずすことにより、実区間多項式r₀(x)+Σ[l_i, h_i]r_i(x)を生成する。生成した実区間多項式の各区間係数の区間幅を単位長に正規化してp₀(x)+Σ[0, 1]p_i(x)と書換え、凸多面体とみなす。超立方体からこの凸多面体への全射となるアフィン写像を取り、超立方体の面のうちアフィン写像により写したものが凸多面体のファセットとなる場合に、このファセットを含む超平面と、それと平行な超平面でファセットと平行な別のファセットを含むものを求め、この２つの超平面の間に点０が存在するか否かを判定することにより、実因子を持つか否かを判定する。 （もっと読む）