簡単さ・難しさの定量 - ryamadaのコンピュータ・数学メモ

興味深い話がある(こちら)
$ax^2+bx+c=0$ で、xの定義域が決められているときに係数a, b, cを求める場合と、逆にa, b, cの範囲が決められていて、xの値を求める場合とでは、どちらが『簡単か・難しいか』？
という問題があった。
変数の数は $t_1=a,t_2=b,t_3=c,t_4=x^2,t_5=x$ の５つだろうか
の定義域が上限と下限で決まっていれば、第一問は以下の４制約。２つの等式制約と２つの不等式制約
- $t_1 t_4 + t_2 t_5 + t_3=0$
- $t_4=t_5^2$
- $t_5\ge t_{5,L}$
- $t_5\le t_{5,U}$
の制約が上限と下限で決まっていれば、第二問は以下の６制約。２つの等式制約と６つの不等式制約
- $t_1 t_4 + t_2 t_5 + t_3=0$
- $t_4=t_5^2$
- $t_1\ge t_{1,L}$
- $t_1\le t_{1,U}$
- $t_2\ge t_{2,L}$
- $t_2\le t_{2,U}$
- $t_3\ge t_{3,L}$
- $t_3\le t_{3,U}$
もし、２つの設問の難易度が定量できるとすれば、「変数の数〜考える空間の次元」と、そこに置かれる制約に対する亜次元多様体(点・線・面・・・)なので、それによって決まりそうだ
変数の制約範囲が片側のみだったり、複数区間だったりしたときにも、制約総数とその等式・不等式内訳とが問題になりそうだ
また、こういうことを考えるときに、等式・不等式以外の制約があるのかどうかも不勉強でわからない
多様体の変数表現と多様体の複雑度とに対応があることを前提にしているけれど、それも、そんなに簡単なのか不明
また、解析的に解くことの難易度として考えているけれど、解き方を変えたら難易度も変わる？もし変わるなら、それはなぜ？
たぶん、「本質的な難易度」は解き方によらず同じになる。逆に言えば、解き方に依存しない難易度の定義は「本質的」であることの必要条件だったりするのだろう