Temukan polinomial dalam dua atau tiga pertanyaan

Kotak hitam $f(x)$ berarti saya dapat mengevaluasi polinom pada titik mana pun. $f(x)$

Input : Kotak hitam polinomial monik derajat . $f(x) \in\mathbb{Z}^+[x]$ $d$
Output: The koefisien polinomial . $d$ $f(x)$

Algoritme saya: biarkan

f (x) = x^{d} + a_{d - 1} x^{d - 1} + \dots + a_{1} x + a_{0}

$f(x) = x^{d} + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$

Mengevaluasi polinomial pada banyak titik menggunakan kotak hitam dan mendapatkan sistem persamaan linear. Sekarang saya dapat memecahkan sistem persamaan linear untuk mendapatkan koefisien yang diinginkan. $\mathcal{f(x)}$ $d$

Namun, dalam hal ini, saya perlu banyak pertanyaan ke kotak hitam. Saya ingin meminimalkan jumlah pertanyaan . Apakah ada cara untuk mengurangi jumlah kueri menjadi hanya dua atau tiga? $\mathcal{O(d)}$

algorithms polynomials Kompleksitas
sumber

Anda terus mengubah pertanyaan. Mungkin Anda harus memutuskan dulu pertanyaan Anda dan baru kemudian menanyakannya. Kalau tidak, itu bisa membuat frustasi penjawab.

Yuval Filmus

Apa artinya

Z^{+}

$\mathbb{Z}^+$

md5

set bilangan bulat positif

Kompleksitas

BTW untuk algoritma Anda, koefisien dapat dihitung dalam

bukan

dengan rumus tertutup Lagrange.

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

md5

Persis pertanyaan yang sama, dengan kata berbeda: math.stackexchange.com/questions/446130/…

Nayuki

Jawaban:

Anda dapat menentukan polinomial menggunakan dua kueri. Pertama kueri polinomial pada untuk mendapatkan batas atas pada nilai koefisien. Sekarang query polinomial di pilihan Anda dan bacalah koefisien dari basis ekspansi. $x=1$ $M$ $x > M$ $x$

Anehnya, jika Anda mengizinkan koefisien negatif maka Anda tidak bisa melakukan lebih baik daripada query. Memang, aku selalu bisa menjawab Anda query dengan nol, dan ini tidak memperbaiki nilai polinomial karena semua polinomial dalam bentuk konsisten dengan jawaban saya. $d$ $d-1$ $x_1,\ldots,x_{d-1}$ $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$

Yuval Filmus
sumber

Untuk negatif saya pikir jenis komplemen 2 trik dapat bekerja.

Kompleksitas

Bukan tanpa batas atas pada besarnya koefisien. Inilah yang ditunjukkan oleh bukti saya.

Yuval Filmus

Maaf saya tidak mendapatkan bagian ini "Aku selalu bisa menjawab Anda

query

dengan nol"

d - 1

$d-1$

x_{1}, \dots, x_{d - 1}

$x_1,\ldots,x_{d-1}$

Kompleksitas

Ini adalah argumen musuh. Algoritme Anda meminta kotak hitam untuk nilai

pada

tempat, dan selalu menjawab nol. Saya menunjukkan bahwa ini tidak cukup bagi Anda untuk menyimpulkan nilai

f

$f$

d - 1

$d-1$

f

$f$

Yuval Filmus