Saya harap pertanyaan ini tidak terlalu naif untuk situs ini. Dalam matematika (topologi, geometri, aljabar) adalah umum bagi seseorang untuk membedakan antara dua objek dengan menghasilkan invarian aljabar atau numerik, dan membuktikan bahwa dua objek memiliki nilai yang berbeda. Saya...
Bahasa whileprogram dapat mengekspresikan fungsi yang dapat dihitung secara komputasi. (Ini benar bahkan jika satu-satunya operasi aritmatika pada variabel adalah, katakanlah, kenaikan dan pengurangan.) Jika whiledigantikan oleh for, membuat loop selalu dibatasi, bahasa kemudian hanya dapat...
Apa yang ada beberapa aplikasi dekomposisi grafik modular dalam teori kompleksitas / TCS? Saya terutama tertarik pada penggunaannya dalam bukti atau batas atas / bawah jika itu terjadi. [1] Dekomposisi grafik modular , Wikipedia. [2] Referensi untuk Dekomposisi Modular ,
Saat mempelajari masalah dalam teori permainan algoritmik, saya tertarik pada kompleksitas pertanyaan pengoptimalan berikut: Masalah Diberikan: set tanah diberikan oleh n ,U= [ n ] = { 1 , ... , n }U=[n]={1,…,n}U = [n] = \{1,\ldots,n\}nnn peringkat diberikan sebagai total pesanan ⟨ S i , σ i...
Saya membaca buku terkenal Alon and Spencer tentang metode probabilistik dalam kombinatorik. Apakah ada survei atau catatan kuliah tentang kemajuan dan hubungan terkini dengan topik teoretis kompleksitas metode berikut di luar buku teks ini? generator pseudorandom membodohi model perhitungan...
Pertimbangkan bahasa . Tentukan (urutan bit tak terbatas) dengan rumus rekursifs ( L ) ∈ { 0 , 1 } ωL.LLs ( L ) ∈ { 0 , 1 }ωs(L)∈{0,1}ωs(L) \in {\lbrace 0, 1 \rbrace}^\omega s ( L )n= χL.( S ( L )<
Ini dimotivasi oleh pertanyaan saya sebelumnya, algoritma perkiraan waktu Super-polinomial untuk MAX-3SAT . Untuk banyak masalah pengoptimalan, untuk masing-masing masalah ini kita memiliki kemungkinan yang tidak dapat diperkirakan sebagai batas bawah dengan asumsi beberapa dugaan teori...
Untuk dapat menjelaskan masalah P vs NP kepada non-matematikawan, saya ingin memiliki contoh pedagogis tentang kapan pencarian Brute Force dapat dihindari. Masalahnya idealnya harus segera dimengerti dan triknya seharusnya tidak terlalu mudah atau terlalu sulit. Yang terbaik yang saya hasilkan...
Dalam makalah "Pengkodean CNF yang Efisien untuk Memilih 1 dari Objek N", para penulis memperkenalkan teknik "variabel komandan" mereka untuk mengkodekan kendala, dan kemudian berbicara tentang masalah lubang kubah. Karena kesalahan saya mungkin ada dalam pemahaman tingkat rendah, izinkan saya...
Jawaban yang Diterima Jawaban Scott Aaronson telah "diterima" (terutama karena itu satu - satunya jawaban!) Ringkasan jawaban satu kalimat Generalisasi yang wajar dan wajar dari pertanyaan P versus NP tidak jelas lebih mudah diselesaikan daripada P versus NP itu sendiri. Satu halangan terhadap...
Saat mendiskusikan pertanyaan yang saya ajukan di sini , @NealYoung dan saya menghadapi masalah lain, yaitu menilai kompleksitas masalah di bawah ini: Diberikan grafik yang tidak terarah yang terhubung, menemukan subset ukuran-maksimum dari tepi sedemikian rupa sehingga setiap simpul memiliki...
Teori kompleksitas tampaknya dibangun di sekitar masalah keputusan daripada fungsi. Siapa yang memperkenalkan ini terlebih dahulu dan apa alasan pilihan ini? Misalnya, kertas "Jalur, pohon, dan bunga" Edmond umumnya dikreditkan sebagai sumber gagasan mewakili sekumpulan masalah "yang dapat...
Mari tentukan masalah SAT: Diberikan , rumus 3-CNF yang memuaskan, dan , rumus 2-CNF ( dan didefinisikan pada variabel yang sama). Apakah memuaskan?( 3 , 2 )s(3,2)s(3,2)_sF3F3F_3F2F2F_2F3F3F_3F2F2F_2F3∧ F2F3∧F2F_3 \wedge F_2 Apa kompleksitas masalah ini? (Apakah sudah dipelajari...
Saya tertarik pada bagaimana seseorang membuktikan bahwa kalimat itu relativis. Tentu saja, membuktikan bahwa sebuah kalimat tidak terelatifkan adalah sederhana, seperti yang terlihat dalam hasil Baker-Gill-Solovay; tetapi bagaimana seseorang membuktikan bahwa suatu kalimat memang relatif, yaitu,...
Saat menelusuri posting CStheory.se lama , saya menemukan posting blog yang menarik tentang masalah kematian matriks . Kecuali saya salah mengartikan masalah, ini menyatakan bahwa dengan memberikan koleksi terbatas matriks 3 x 3 dengan entri integer untuk setiap nilai matriks, kita harus memutuskan...
Diberi grafik , berapakah jumlah minimum tepi yang perlu kita hapus untuk membuat segitiga grafik bebas? Bagi mata saya yang tidak terlatih, ini tampaknya merupakan masalah yang sulit.GGGGGG Apakah masalah ini diketahui sebagai NP-complete? Bagaimana dengan analog untuk grafik berorientasi (yaitu,...
(Saya memposting pertanyaan ini di CS sepuluh hari yang lalu, tanpa jawaban sejak saat itu - jadi saya posting di sini.) Setiap rumus CNF dapat diubah dalam waktu polinomial menjadi rumus 3-CNF dengan menggunakan variabel baru. Tidak selalu mungkin jika variabel baru tidak diperbolehkan (misalnya,...
Saya mencari referensi tentang `mengurangi 'pengurangan Turing ke banyak-satu pengurangan. Dalam benak saya ada pernyataan tentang bentuk berikut (pernyataan yang serupa juga akan memuaskan saya): Dalil. Jika , maka A ≤ 2 f m B t t .A≤fTBA≤TfB\mathsf{A}\leq_T^f \mathsf{B}A≤2fmBttA≤m2fBtt\mathsf...
Apa algoritma tercepat yang dikenal untuk memfaktorkan polinomial dengan variabel dan derajat total ≤ d ? Di sini, n tumbuh dan d diperbaiki. Sebagian besar pekerjaan tampaknya mempertimbangkan kasus ketika d tumbuh dan n diperbaiki. Saya tertarik pada hasil, baik di bidang terbatas maupun...
Salah satu cara untuk membuktikan NP CoNp adalah untuk menunjukkan bahwa untuk setiap sistem bukti proposisi dihitung dalam waktu polinomial, terdapat sebuah keluarga tautologies yang membutuhkan panjang bukti yang super polinomial (wrt panjang tautologi yang terbukti). Hasil seperti itu dari Haken...