Pertanyaan yang diberi tag reductions

Dalam teori komputasi dan kompleksitas (dan mungkin bidang lainnya), reduksi ada di mana-mana. Ada banyak jenis, tetapi prinsipnya tetap sama: menunjukkan bahwa satu masalah setidaknya sekeras beberapa masalah lainnya dengan memetakan contoh dari ke yang setara dengan solusi di . Pada dasarnya,...

Wikipedia serta sumber lain yang saya temukan daftar voidtipe C sebagai tipe unit sebagai lawan dari tipe kosong. Saya menemukan ini membingungkan karena menurut saya voidlebih cocok dengan definisi tipe kosong / bawah. Tidak ada nilai yang dihuni void, sejauh yang saya tahu. Suatu fungsi dengan...

Saya mengambil kursus kompleksitas dan saya mengalami masalah dengan datangnya pengurangan antara masalah NPC. Bagaimana saya bisa menemukan pengurangan di antara masalah? Apakah ada trik umum yang bisa saya gunakan? Bagaimana saya harus mendekati masalah yang meminta saya untuk membuktikan masalah...

Saya tertarik pada pertanyaan tentang cara terbaik untuk mengajarkan kelengkapan NP ke jurusan ilmu komputer. Secara khusus, haruskah kita mengajarkannya menggunakan pengurangan Karp atau menggunakan pengurangan Turing? Saya merasa bahwa konsep pelengkapan dan pengurangan NP adalah sesuatu yang...

Sejumlah masalah mengejutkan memiliki pengurangan yang cukup alami untuk pemrograman linier (LP). Lihat Bab 7 dari [1] untuk contoh-contoh seperti aliran jaringan, pencocokan bipartit, permainan zero-sum, jalur terpendek, bentuk regresi linier, dan bahkan evaluasi sirkuit! Karena evaluasi...

Katakanlah ada program sedemikian rupa sehingga jika Anda memberikan Sudoku yang terisi sebagian dari ukuran apa pun, itu memberi Anda Sudoku lengkap yang sesuai. Bisakah Anda memperlakukan program ini sebagai kotak hitam dan menggunakannya untuk menyelesaikan TSP? Maksud saya, apakah ada cara...

Apa yang ingin saya lakukan adalah mengubah masalah matematika yang saya miliki menjadi masalah kepuasan boolean (SAT) dan kemudian menyelesaikannya menggunakan SAT Solver. Saya ingin tahu apakah seseorang mengetahui manual, panduan, atau apa pun yang akan membantu saya mengubah masalah saya...

Masalah subset-jumlah adalah masalah klasik NP-complete: Diberikan daftar angka dan target , adakah subset angka dari yang menjumlahkan ke ?k L kL.LLkkkL.LLkkk Seorang siswa bertanya kepada saya apakah varian masalah yang disebut masalah "subset produk" ini adalah NP-complete: Diberikan...

Inilah masalahnya. Diberikan , di mana setiap . Apakah ada subset dengan ukuran paling banyak sehingga untuk semua ? Saya mencoba mengurangi masalah ini menjadi SAT. Gagasan saya tentang solusi adalah memiliki variabel untuk masing-masing 1 hingga . Untuk setiap , buat klausa jika . Kemudian dan...

Wikipedia menyatakan masalah jumlah subset sebagai menemukan subset dari multiset integer yang diberikan, yang jumlahnya adalah nol. Lebih lanjut ia menyatakan bahwa itu sama dengan menemukan subset dengan jumlah untuk setiap diberikan .ssssss Jadi saya percaya karena keduanya setara, harus ada...

Mungkin ini cukup sederhana tetapi saya memiliki beberapa kesulitan untuk mendapatkan pengurangan ini. Saya ingin mengurangi Jumlah Subset ke Partisi tetapi saat ini saya tidak melihat hubungannya! Apakah mungkin untuk mengurangi masalah ini menggunakan Pengurangan Levin? Jika Anda tidak mengerti...

Mari saya mulai dengan mencatat bahwa ini adalah masalah pekerjaan rumah, tolong berikan hanya saran dan pengamatan terkait, JANGAN JAWABAN LANGSUNG . Dengan itu, inilah masalah yang saya lihat: Biarkan HALF-CLIQUE = { | adalah grafik tak berarah yang memiliki subgraph lengkap dengan setidaknya...

Dalam tulisan Complexity of the Frobenius Problem oleh Ramírez-Alfonsín, masalah terbukti sebagai NP-complete menggunakan pengurangan Turing. Apakah itu mungkin? Bagaimana sebenarnya? Saya pikir ini hanya mungkin dengan pengurangan banyak waktu polinomial. Apakah ada referensi tentang ini? Apakah...

Buku-buku teks di mana-mana mengasumsikan bahwa Masalah Korespondensi Bounded Post adalah NP-complete (tidak lebih dari NNN indeks diizinkan dengan pengulangan). Namun, tidak ada satupun yang menunjukkan pengurangan polinomial waktu yang sederhana (seperti pada, sesuatu yang dapat dipahami oleh...

Berkat teorema min-cut max-flow, kami tahu bahwa kami dapat menggunakan algoritma apa pun untuk menghitung aliran maksimum dalam grafik jaringan untuk menghitung a -min-cut. Oleh karena itu, kompleksitas penghitungan potongan minimum ( s , t ) tidak lebih dari kompleksitas penghitungan aliran...

Saya berjuang untuk memahami hubungan antara NP-Intermediate dan NP-Complete. Saya tahu bahwa jika P! = NP berdasarkan Teorema Ladner ada kelas bahasa dalam NP tetapi tidak dalam P atau NP-Lengkap. Setiap masalah dalam NP dapat direduksi menjadi masalah NP-Complete, namun saya belum melihat contoh...

Sebuah Hidoku adalah grid dengan beberapa bilangan bulat pra-diisi dari 1 sampai n 2 . Tujuannya adalah untuk menemukan jalur bilangan bulat berturut-turut (dari 1 hingga n 2 ) di grid. Lebih konkret, setiap sel grid harus mengandung bilangan bulat yang berbeda dari 1 ke n 2 dan setiap sel dengan...

Misalkan A direduksi ke B, yaitu, . Oleh karena itu, mesin Turing menerima A memiliki akses ke oracle untuk B . Biarkan Turing mesin menerima A menjadi M A dan oracle untuk B menjadi O B . Jenis pengurangan:A≤BA≤BA \leq BAAABBBAAAMAMAM_{A}BBBOBOBO_{B} Turing pengurangan: dapat membuat beberapa...

Rupanya, jika P=NPP=NP{\sf P}={\sf NP} , semua bahasa dalam PP{\sf P} kecuali ∅∅\emptyset dan Σ∗Σ∗\Sigma^* akan menjadi NPNP{\sf NP} -lengkap. Mengapa dua bahasa ini khususnya? Tidak bisakah kita mengurangi bahasa lain dalam PP{\sf P} ke mereka dengan mengeluarkannya saat menerima atau tidak...

Kami memiliki DAG. Kami memiliki fungsi pada node F: V→ NF:V→NF\colon V\to \mathbb N (secara longgar, kami beri nomor pada node). Kami ingin membuat grafik terarah baru dengan aturan ini: Hanya node dengan nomor yang sama dapat dikontrak ke node baru yang sama. F( x ) ≠ F( y) ⇒ x′≠...