Kompleksitas Peringkat Tensor di Bidang yang Tak Terbatas

Sebuah tensor adalah generalisasi dari vektor dan matriks untuk dimensi yang lebih tinggi dan peringkat dari tensor juga generalizes pangkat matriks. Yakni, peringkat dari tensor adalah jumlah minimal peringkat satu tensor bahwa jumlah untuk . Vektor dan matriks masing-masing adalah tensor derajat 1 dan 2. $T$ $T$

Unsur-unsur di berasal dari bidang . Jika adalah terbatas, maka Håstad membuktikan bahwa memutuskan apakah pangkat tensor derajat 3 paling banyak adalah NP-complete, tetapi ketika adalah bidang tak hingga seperti rasional , ia memberi (atau mengutip) tidak ada batas atas. $T$ $\mathbb{F}$ $\mathbb{F}$ $r$ $\mathbb{F}$ $\mathbb{Q}$

Pertanyaan: Apa batas atas yang paling dikenal untuk kerumitan dalam menentukan apakah peringkat dari tensor 3 pada paling banyak ? $T$ $\mathbb{Q}$ $r$

ds.algorithms reference-request computability tensor-rank Tyson Williams
sumber

Apakah pangkat bertingkat tiga lebih over sama dengan pangkat tensor yang sama lebih dari ℝ? Jika demikian, masalahnya dapat dirumuskan sebagai kasus khusus dari Teori Eksistensial dari Rals dan karena itu terletak di PSPACE.

Tsuyoshi Ito

Gagasan dalam komentar saya sebelumnya tidak akan berfungsi karena pangkat tensor derajat tiga di atas ℚ terkadang berbeda dari pangkat tensor yang sama di atas ℝ. Biarkan {x, y} menjadi dasar ruang vektor dua dimensi, dan pertimbangkan tensor 2x⊗x⊗x + x⊗y⊗y + y⊗x⊗y + y⊗y⊗x. Tidak sulit untuk melihat bahwa peringkatnya di atas ℝ adalah dua tetapi peringkatnya di atas ℚ lebih besar dari dua. (Contoh ini diperoleh dengan memodifikasi contoh yang menunjukkan bahwa peringkat di atas ℝ dapat berbeda dari peringkat di atas ℂ di Kruskal 1989. )

Tsuyoshi Ito

@ Tsuyoshi Ito Saya sepenuhnya setuju. Saya juga tidak dapat menemukan batas atas.

Tyson Williams

Saya pikir lebih baik meminta komputabilitas sebelum kompleksitas.

Tsuyoshi Ito

The upperbound sepele adalah bahwa hal itu ce Håstad juga membuktikan di koran yang sama bahwa masalah adalah

atas

. Masalah yang lebih umum berikut adalah lengkap: diberikan tensor terisi sebagian, adakah penyelesaiannya yang memiliki peringkat

N P - h a r d

$\mathsf{NP\text{-}hard}$

Q

$\mathbb{Q}$

\leq r

$\leq r$

Kaveh

Jawaban:

Ada pracetak baru-baru ini tentang ini: http://galton.uchicago.edu/~lekheng/work/np.pdf . Hal ini menunjukkan bahwa sebagian besar isu-isu terkait peringkat-dengan tensor yang NP keras selama dan . (Itu juga menyebutkan bahwa menentukan peringkat di atas adalah NP sulit.) $\mathbb{R}$ $\mathbb{C}$ $\mathbb{Q}$

Bart
sumber

Bart, cetakan itu (oleh Hillar dan Lim) luar biasa ... terima kasih banyak.

John Sidles

Bagus. Namun, saya tidak mengerti kalimat ini: "Sementara hasil Håstad berlaku untuk

dan

, pilihan bidang ini tidak masuk akal untuk semua kecuali satu dari masalah di atas (pengecualian menjadi sistem persamaan bilinear) karena ini adalah masalah analitik hanya didefinisikan dengan baik pada bidang karakteristik lengkap 0 dengan nilai absolut. Di antara bidang tersebut,

dan

sejauh ini merupakan yang paling umum dalam aplikasi dan karenanya kami akan membatasi diskusi kami pada bidang ini. "

Q

$\mathbb{Q}$

F_{q}

$\mathbb{F}_q$

R

$\mathbb{R}$

C

$\mathbb{C}$

Tyson Williams

Salah satu masalah yang dimaksud dalam kutipan di atas adalah peringkat. Apakah penulis ini mengatakan bahwa peringkat tensor tidak didefinisikan dengan baik di atas

Q

$\mathbb{Q}$

Tyson Williams

@Tyson: Saya pikir penulis hanya ingin mengatakan bahwa untuk banyak aplikasi numerik (persamaan diferensial parsial, pemrosesan sinyal), Anda ingin melakukan perhitungan di

atau

. Menjadi seorang analis numerik sendiri, saya tidak melihat banyak aplikasi didefinisikan pada

. Mereka tidak menyiratkan rank yang tidak didefinisikan dengan baik pada

R

$\mathbb{R}$

C

$\mathbb{C}$

Q

$\mathbb{Q}$

Q

$\mathbb{Q}$

Bart

Meskipun ini benar-benar satu-satunya jawaban (karena John bermaksud untuk berkomentar), saya masih percaya jawaban ini pantas mendapatkan karunia karena memberikan referensi yang menunjukkan kekerasan terhadap bidang tak terbatas penting lainnya (real dan kompleks). Seperti yang ditunjukkan oleh judul pertanyaan saya, saya ingin tahu tentang bidang yang tidak terbatas pada umumnya tetapi memutuskan untuk bertanya tentang alasan agar memiliki pertanyaan dengan jawaban yang spesifik. Saya masih akan memilih pertanyaan lain sebagai jawaban yang diterima jika seseorang dapat memberikan batas atas (atau menunjukkan bahwa itu tidak dapat dihitung).

Tyson Williams

Buku Perspektif dalam Kompleksitas Komputasi: Volume Peringatan Hari Jadi Somenath Biswas yang diterbitkan musim panas ini (Juli 2014) sebagian besar setuju dengan konsensus yang kami capai di sini. Di halaman 199 , tertulis:

$\mathbb{Q}$ $\mathbb{R}$

Tyson Williams
sumber

Pracetak baru-baru ini juga mengkonfirmasi ini: arxiv.org/pdf/1612.04338v1.pdf . (Lihat tabel di halaman 3.)

Huck Bennett

Catatan: Teks di bawah ini dimaksudkan sebagai komentar ... jelas bukan jawaban, melainkan pengamatan pragmatis yang muncul dari ulangan Prinsip - prinsip Resonansi Magnetik Charlie Slichter dalam bahasa geometri simptektik dan teori informasi kuantum (yang menarik kembali secara alami ke ruang-produk negara-peringkat polinomial-peringkat). Saat ini kami memiliki pemahaman geometris parsial dari metode tensor-rank ini, pemahaman informatif kuantum marjinal, pada dasarnya tidak ada pemahaman kompleksitas-teoretis atau kombinatorik, dan pemahaman komputasi yang bekerja (tetapi sebagian besar bersifat empiris).

Kami sangat tertarik untuk memperluas, memperdalam, dan menyatukan pemahaman ini, jadi kami berharap orang lain akan mengirim jawaban / komentar lebih lanjut tentang hal ini.

C

$\mathbb{C}$

John Sidles
sumber

Apakah teorema ini mudah dinyatakan? Jika tidak, dapatkah Anda memberikan tautan ke pernyataan dan penjelasan yang baik?

Tyson Williams

@Tyson: Saya pikir John berbicara tentang pengalamannya memecahkan contoh masalah, dan bukan tentang teorema.

Joe Fitzsimons

Anda bertanya kepadanya tentang teorema, dan sepertinya dia tidak membicarakannya. Saya hanya berpikir Anda salah paham tentang dia.

Joe Fitzsimons

Sebenarnya, saya pikir saya telah mengirim komentar & terkejut melihatnya muncul sebagai jawaban. Doh! Saya baru saja mengeditnya untuk menambahkan referensi, tetapi masih sangat jauh dari jawaban yang memuaskan. Sebuah pertanyaan bagus oleh Tyson Williams! :)

John Sidles

@Joe Dia menyebutkan teorema kelengkungan holomorfik Goldberg dan Kobayashi, jadi saya bertanya kepadanya tentang hal itu. Saya tidak yakin apakah itu berarti saya salah paham atau tidak.

Tyson Williams