- ベストアンサー
多項式時間変換についての質問
Tacosanの回答
あ, すみません, 間違えました. この内容は「多項式時間変換」に限定したものです. 「多項式時間還元」で一般的に成り立つものではありません. 既に書いたように, 「A から B に多項式時間還元できる」というのは「B を解くオラクルがあれば A を多項式時間で解くことができる」ということです. B を解くオラクルを使うためには, 与えられた A の問題例から B の問題例を (多項式時間で) 作る必要がありますが, B の問題例を「1個だけ」作るとは限りませんし, 与えられた A の問題例の答え (yes/no) が作られた B の問題例の答え (yes/no) と一致する必要もありません. 極端にいえば, 問題 A とその補問題 A' (A の yes/no を反転した問題) があれば, 「A から A' に多項式時間還元できる」ことになります. つまり, A の問題例 x が与えられたときに, A' を解くオラクルに x を与えます. すると yes/no が得られるわけですが, これは A の問題例としての yes/no とはちょうど正反対です. つまり, 「A' を解くオラクルに x を与えて得られる答え」の yes/no を反転すればよく, これは「A' を解くオラクルを用いた A の多項式時間アルゴリズム」です. まあ, 普通「A が B に還元できる」ということを示すときには「A から B への変換」を作る (つまり「A から B に変換できる」から「還元可能」ということを示す) んですけど, 一般論として「常に変換が作れる」とは限りません. ちなみに「多項式時間還元」と「多項式時間変換」を同じ意味で使うときには, どちらも「多項式時間還元」の意味で使うんじゃないかなぁ.
関連するQ&A
- 多項式の一番簡単な解き方
たとえば、6x^4-11x^3+x^2+33x-45=0 という多項式を解くときに、私はいつも解をひとつ見つけてから、徐々にXの係数を少なくして解いていくやり方をしています。 しかしこの、ひとつ解を見つけるという作業が非常に時間がかかってしまい(ただ数を式に当てはめて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はチェックボックスにチェックが入っている状態です テーブル ---------------------------------------------- グループ 分類1 分類2 分類3 ---------------------------------------------- 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 上記のようなテーブルがあります。これを ----------------------------------------------------- グループ グループ総数 分類1 分類2 分類3 ----------------------------------------------------- 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フィールドの合計を 表示してきました。 なにか他の方法でスマートなやり方や関数はないのでしょうか。 もしくは上記方法で間違いないのでしょうか。 宜しくお願い致します。
- ベストアンサー
- その他(データベース)
- 3次の多項式が重解をもつ条件
以下問題文です。 3次の多項式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の解を全て求めよ。 三次関数のグラフを漠然と思い浮かべ微分を試みたものの 具体的な方針には結びつかず滞っています。 どなたか,動機を教授頂きたいと思います。
- ベストアンサー
- 数学・算数
お礼
なんとなくわかりました。つまり多項式時間還元で 解の一致が求められるのは、変換と還元を同じ意味で使っていたからなんですね。別々の意味だと還元はAの補問題A'にも還元できるし、解が一致する必要もない。またBの問題例を複数個作る事も可能なのですね。 色々有難うございました。アドバイス助かりました。