Decidability of Equality of Radical Expressions

8

Pertimbangkan istilah yang dibangun dari elemen Q dan operasi +,×,,/, dan n untuk setiap bilangan alami n. Mengingat janji bahwa dua istilah terbentuk dengan baik - yaitu, tidak ada pembagian dengan nol, dan bahkan tidak ada akar angka negatif - apakah ada algoritma yang memutuskan kapan kedua istilah itu sama?

Pertanyaan terkait telah diposting di sini , tetapi lebih umum (karena memungkinkan eksponensial sewenang-wenang, bukan hanya dengan angka-angka rasional).

Mees de Vries
sumber
Apa yang kamu pikirkan? Apa yang sudah Anda coba dan di mana Anda terjebak?
Raphael
@ Raphael, untuk lebih jelasnya, ini bukan pekerjaan rumah atau penelitian - ini hanya masalah pikiran kosong. Saya belum memikirkan hal ini. Jelas ini sepele tanpa akar. Saya cukup yakin setQ-polinomial masuk nAkar bilangan bulat memiliki kesetaraan yang dapat ditentukan, karena memeriksa QKemandirian linear dari akar tersebut harus mudah (?). Tapi saya benar-benar terjebak ketika datang ke radikal bersarang, atau bahkan sebagian kecil dari "polinomial radikal 'seperti itu.
Mees de Vries

Jawaban:

3

Iya. Dengan analog bilangan real dari transformasi Tseytin , yang
mereduksi ke teori eksistensial real , yang ada di PSPACE oleh

halaman 291 dan bagian bawah halaman 290 dari makalah ini
dan
jawaban untuk pertanyaan ini

.


Untuk semua bilangan realx, x2 dan x keduanya terbentuk dengan baik dan x2=x Jika dan hanya jika 0x, Jadi menguji ketimpangan mengurangi masalah Anda. Saya tidak mengetahui adanya batas atas yang lebih baik untuk menguji ketidaksetaraan jumlah akar kuadrat dari makalah ini , yang menempatkannya dalam hierarki penghitungan .

Komunitas
sumber
Bagus, tapi mengapa Anda meletakkan baris baru sebelum titik? Saya mencoba mengkompilasi kode spasi putih Anda, tetapi tidak berhasil.
Jahat
Terima kasih atas jawabannya! Kami berharap referensi memenuhi persyaratan ilmiah minimal dan sekuat mungkin dari waktu ke waktu. Silakan luangkan waktu untuk memperbaiki posting Anda dalam hal ini. Kami telah mengumpulkan beberapa saran di sini . Terima kasih!
DW
3
  1. Bilangan aljabar adalah solusi polinomial dengan koefisien rasional.
  2. +,×,,/angka aljabar menghasilkan angka aljabar karena angka aljabar membentuk bidang ( 1 ). Ini berarti radikal bersarang adalah angka aljabar juga ( 2 ).
  3. Radikal bersarang dapat dibantah dengan algoritma ( 3 , 4 ).
  4. Setiap jumlah derajat aljabar n dapat secara unik direpresentasikan sebagai n oleh n matriks bilangan bulat di bawah dasar yang sesuai (misalnya, [1,x,(x2+1)/2]). Representasi ini memungkinkan evaluasi simbolis+,×,,/oleh penambahan matriks, perkalian, dan kebalikan (p.159 dari 5 , 6 , 7 ).
  5. Dua istilah sama jika representasi uniknya identik.
titik titik titik
sumber
Saya merasa seperti bagian penting / menarik di sini adalah algoritma denesting; sisanya bekerja (bahkan tanpa algoritma denesting, karena radikal bersarang jelas aljabar bahkan jika Anda tidak tahu bagaimana membenci mereka), tetapi merupakan semacam meriam untuk lalat.
Mees de Vries
Terima kasih atas jawabannya! Kami berharap referensi memenuhi persyaratan ilmiah minimal dan sekuat mungkin dari waktu ke waktu. Silakan luangkan waktu untuk memperbaiki posting Anda dalam hal ini. Kami telah mengumpulkan beberapa saran di sini . Terima kasih!
DW