Judulnya kurang lebih menyebutkan semuanya, tapi saya rasa saya bisa menambahkan sedikit latar belakang dan beberapa contoh spesifik yang saya minati.
Para ahli teori kompleksitas deskriptif, seperti Immerman dan Fagin, telah mengkarakterisasi banyak kelas kompleksitas yang paling terkenal menggunakan logika. Misalnya, NP dapat dikarakterisasi dengan kueri eksistensial orde dua; P dapat dikarakterisasi dengan kueri urutan pertama dengan ditambahkan operator titik paling tidak tetap.
Pertanyaan saya adalah: Pernahkah ada upaya, terutama yang berhasil, dalam menghadirkan representasi seperti itu untuk kelas kompleksitas kuantum, seperti BQP atau NQP? Jika tidak, mengapa tidak?
Terima kasih.
Pembaruan (moderator) : pertanyaan ini sepenuhnya dijawab oleh posting ini di mathoverflow .
Jawaban:
Saya pikir jawaban Robins ini untuk pertanyaan saya di MO juga menjawab satu ini.
Sebuah kompleksitas deskriptif karakterisasi kelas kompleksitas memberikan bahasa yang query (yaitu formula) yang persis fungsi komputasi di C . Sintaks bahasa biasanya sangat sederhana, yaitu diberi string q mudah untuk memeriksa apakah q adalah permintaan yang terbentuk dari bahasa, setidaknya itu diharapkan dapat dipilih (tetapi biasanya sintaks memeriksa dapat dilakukan dalam kelas kompleksitas kecil). Ini akan memerlukan enumerablity efektif masalah di kelas C dan akan memberikan karakterisasi sintaksis untuk C . (Jika kompleksitas pemeriksaan sintaksis rendah, ini mungkin juga menyiratkan adanya masalah lengkap untuk kelas.)C C q q C C
Dalam komentar di atas, Robin terkait dengan Kord Eickmeyer dan kertas Martin Grohe ini " Pengacakan dan Derandomization di Deskriptif Kompleksitas Teori " yang memberikan "kompleksitas deskriptif" karakterisasi . Para penulis sendiri mencatat dalam pengantar bahwa ini berbeda dari apa yang biasanya dimaksud dengan karakterisasi kompleksitas deskriptif:BPP
Saya bukan ahli dalam teori model hingga / kompleksitas deskriptif (dan secara pribadi ingin mendengar lebih banyak dari para ahli), tetapi perasaan saya adalah bahwa ada sedikit kecurangan di sini dengan mengatakan bahwa ini adalah karakterisasi kompleksitas deskriptif. Alasan perasaan saya adalah bahwa jika kita diizinkan memiliki sintaksis yang tidak efektif, kita dapat menggunakan batasan semantik yang arbitrer untuk membatasi kelas kueri yang terbentuk dengan baik dan dapat memberikan karakterisasi "kompleksitas deskriptif" untuk setiap kelas kompleksitas. Sebagai contoh, perhatikan (yang menangkap P S p a c e ), dan kemudian mengambil persis kueri yang dihitung di B Q PSO(TC) PSpace BQP ; atau mempertimbangkan bahasa yang memiliki satu fungsi simbol untuk setiap mesin di . Kedua capture ini B Q P tetapi tidak memiliki sintaks yang efektif.BQP BQP
sumber
sumber