- ベストアンサー
多項式時間変換についての質問
Tacosanの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
とりあえず明らかにしておきたいことがあります: １．「還元」と「変換」が混在しているんですけど, 区別しているんでしょうか? 内容を見る限り区別しないと変な感じはするんですが, 区別していると仮定すると内容がおかしいです. 区別するなら ・A から B に多項式時間還元可能: B を解くオラクルがあれば A は多項式時間で解ける ・A から B に多項式時間変換可能: A の問題例が与えられれば, それと yes/no が一致する B の問題例を多項式時間で生成できる という意味です. ２．yes/no を「解のある/なし」としていますが, これは間違っています. そもそも「与えられた問題例に対して yes/no を答える」という問題ですから, 解はあるに決まっています. その解が yes (問題によって定まる性質を満たす) か no (性質を満たさない) かのどちらかである, ということです. で, 2つ目の問題は「還元」と「変換」を区別していないと意味を持たないんですが, 区別しているなら「普通はなくてもいい」ということになりそう. 「変換」の定義から A の答えが yes iff B の答えが yes なので, (2) と (3) は (yes/no のどちらかに必ず定まるという前提のもとで) 等価です. あと, 1つ目の方は「普通そんな表現はしない」というのが正解かな. 普通は 「A から B に多項式時間還元可能 → B は A と同等以上に難しい」 ですね. 「同等に難しい」ことまでは保証しません. これは「変換」でも同じかな.
関連するQ&A
- 多項式の一番簡単な解き方
たとえば、6x^4-11x^3+x^2+33x-45=0 という多項式を解くときに、私はいつも解をひとつ見つけてから、徐々にＸの係数を少なくして解いていくやり方をしています。 しかしこの、ひとつ解を見つけるという作業が非常に時間がかかってしまい（ただ数を式に当てはめて０になる数を見つけるまでやってるので）困ってます。なにか、数あてのコツなどありませんか？ また他に、もっと速く解ける解き方があったら教えてください。 （ちなみに例に挙げた多項式の解は虚数の解も含んでいます）
- ベストアンサー
- 数学・算数
- 多項式の積が同次にならない
定理の証明がわからなくなったので質問します。 定理 2つの多項式のうち、少なくとも1つが同次でないとき、その積は同次でない。 証明 多項式f,gのうち少なくとも1つ、たとえばfが同次でないとする。f=A+Bとし、Bはfのなかの最低次数の項の和のつくる同次多項式とし、Aはそれ以外の項の和とする。同じく g=A'+B'とし、B'はgなかの最低次数の項の和、A'はそれより高次の項の和とする。もしgが同次式のときはA'=0とする。 f・g=(A+B)(A'+B')=AA'+AB'+BA'+BB'ここでAA'+AB'+BA'の次数はBB'の次数より明らかに高い。よってf・gは同次式ではない。 (証明終了) ここでわからないのは、もしgが同次式のときはA'=0とする。の一文です。たとえばA'=x^2-2xy+5y^2で、B'=x+yのときB'=0でもgが同次式になると思います。なぜgが同次式のときはA'=0に限られるのか知りたいです。また2つ目の疑問として、f,gの2つとも同次式でないときは、どのようにその積は同次でないことを証明するのかも教えていただけると幸いです。どなたかお返事お願いします。
- 締切済み
- 数学・算数
- 代数の既約多項式の問題です。
代数の既約多項式の問題です。 a_n(x^n)＋a_n-1(x^n-1)～＋a_2(x^2)＋a_1(x)＋a_0=0 （a_0,a_1,・・・a_n∈Q:有理数） が既約とする。この方程式の解がn次未満のQ係数多項式の解とはならない事を示せ。 既約多項式:これ以上約せない多項式 わかる方いましたらよろしくお願いいたします。
- ベストアンサー
- 数学・算数
- ACCESS Yes/No型の集計
ACCESSでチェックボックスが複数あるテーブルがあります。これら各々の個数を表示させたいと奮闘しております。複数のフィールドがあるので、やり方をご教授いただけますようお願いいたします。構造とやりたいことは下記に記します Yesはチェックボックスにチェックが入っている状態です テーブル ---------------------------------------------- グループ 分類１ 分類２ 分類３ ---------------------------------------------- A ｜ Yes ｜ No ｜ Yes A ｜ No | No ｜ Yes A ｜ Yes ｜ Yes ｜ No B ｜ Yes ｜ No ｜ Yes B ｜ No ｜ No ｜ Yes B ｜ Yes ｜ No ｜ Yes ・ ・ ・ ZZ 上記のようなテーブルがあります。これを ----------------------------------------------------- グループ グループ総数 分類１ 分類２ 分類３ ----------------------------------------------------- A ｜ 3 ｜ 2 ｜ 1 ｜ 2 B ｜ 3 ｜ 2 ｜ 0 ｜ 3 ・ ・ ・ ZZ とういうようにグループの総数とチェックボックスにチェックが入った数を算出させたいんです どうかご教授願います
- ベストアンサー
- その他MS Office製品
- 多項式を誤解している？
多項式f(x)を求める問題で 条件の一つに x^4f(1/x)=f(x) をf(x)は満たすという条件がありました n>4の範囲では右辺が多項式であるのに、左辺は多項式とならないから、矛盾する よってf(x)の次数は4以下となる(背理法による証明) …と模範回答にあるのですが 多項式って 例えば f(x)=ax^4+b^3+c^2+dx+e みたいなやつですよね？ f(x)=a/x+b+cx+dx^2+ex^3 みたいな分数型が入った式は多項式じゃないんですか？ 多項式って中学生で習うのに、全然理解できてない自分にショックを受けてます。
- ベストアンサー
- 数学・算数
- SQLについて教えてください
こんにちは。 以下のテーブルAがあるとして、 a b 1 No 2 No 3 Yes 4 Yes フィールドbがYesのところだけを+1したいのですが、どのように書けばいいのでしょうか？ 私は、Access2003を使用しています。 すみませんが、宜しくお願いします。
- ベストアンサー
- オフィス系ソフト
- ファイルメーカーについて
またまたファイルメーカー(Pro7)について質問いたします。 例 1つのレコードにYesもしくはNoを選択するAフィールドを作成 1.YES 2.No 3.Yes 4.Yes 5.No Yesの総計3を表示したいのですが、今までは 1つのレコードにもう1つBフィールドを作成 if(B="Yes" ;1;0)関数により答えを導き、 総計フィールド&パートを作成し、Bフィールドの合計を 表示してきました。 なにか他の方法でスマートなやり方や関数はないのでしょうか。 もしくは上記方法で間違いないのでしょうか。 宜しくお願い致します。
- ベストアンサー
- その他(データベース)
- ３次の多項式が重解をもつ条件
以下問題文です。 ３次の多項式f(x)=x^3-a*x^2+b*x-1について次の問いに答えよ。 (1)f(x)=0が重解をもつならば，f(-1)≦0が成り立つことを示せ。 (2)a+b+2=0とする。f(x)=0が重解をもつとき，a，bの値と，f(x)=0の解を全て求めよ。 三次関数のグラフを漠然と思い浮かべ微分を試みたものの 具体的な方針には結びつかず滞っています。 どなたか，動機を教授頂きたいと思います。
- ベストアンサー
- 数学・算数
補足
紛らわしく還元と変換を混同させて申し訳ないのです。 多項式時間変換と多項式時間還元は同じ意味だと解釈してました。 知りたいのは多項式時間還元の方です。 yes,noの意味は、性質を満たすかどうかで解の有る無しではないのですね。言われてみればそう思います。 それで、アドバイスから察すると例えば問題Bがnoならば,問題Bは'解けて' 性質を満たさないことがわかった。なのでAは多項式時間変換+Bのアルゴリズムを使っているのでAも性質を満たさないことがわかる。 つまり「BがnoならAもno」の時でもBは解いているのでAも解けるということなんですね。 最後に、変換の方は証明(3)は「普段はなくてもいい」の意味などは わかりました。それで、還元の方はやはり証明(3)問題Aがyes(no)ならば問題Bもyes(no)の必要性がわかりません。Bが解ければAも解ける事がいえればいいので(1)(2)だけでいいと思うのですが。