| dbo:abstract
|
- مبرهنة كوك ليفين في نظرية التعقيد الحسابي تنص على أن مسألة الاكتفاء (SAT) هي NP كاملة، يعني أنَّ كل مسألة في NP يمكن اختصارها بوقت حدودي بواسطة آلة تيورنج قطعية حدودية لمسألة تحديد إذا ما صيغة بوليانية قابلة للاكتفاء . أحد تبعات هذه المُبرهنة أنه لو وُجدت خوارزمية لحل مسألة الاكتفاء حينها كل لغة في NP يمكن أيضا حلها كذلك بواسطة نفس الخوارزمية وبوقت حدودي والامر ذاته أيضا لكل لغة تابعة ل- NP كاملة . ايجاد هذه الخوارزمية أو برهان عدم وجودها كان الموضوع الاساسي في علم الحاسوب منذ 30 عام وهذه المسألة تسمى مسألة P=NP . هذه المبرهنة سميت على اسم . (ar)
- Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie. Er zeigte, dass eine Teilmenge der Klasse NP existiert, auf die sich alle Probleme aus NP reduzieren lassen. Diese Teilmenge ist damit repräsentativ für die Schwierigkeit von NP und wird als NP-vollständig (NPC für englisch NP complete) bezeichnet. Der nach ihm benannte Satz von Cook sagt aus, dass das Erfüllbarkeitsproblem der Aussagenlogik (SAT, v. engl. satisfiability) NP-vollständig ist. Einen vergleichbaren Satz veröffentlichte Leonid Levin unabhängig von Cook im Jahre 1973, deswegen spricht man manchmal auch vom Satz von Cook und Levin. Mit einem bekannten Vertreter der Klasse war der Nachweis für andere Probleme aus NP wesentlich einfacher zu führen, da es für ein Problem M aus NP nun ausreichte eine polynomielle Reduktion von SAT auf M zu konstruieren, um die NP-Vollständigkeit von M zu beweisen. Richard M. Karp erweiterte 1972 auf diese Weise NPC um 21 weitere Probleme, bis heute wurden mehrere hundert nachgewiesen. (de)
- Στην θεωρία πολυπλοκότητας το θεώρημα Κουκ-Λέβιν (Cook-Levin), το οποίο επίσης είναι γνωστό ως θεώρημα του Κουκ, αναφέρει ότι το είναι NP-πλήρες.Α υτό σημαίνει ότι οποιοδήποτε πρόβλημα στο μπορεί να μειωθεί σε πολυωνυμικό χρόνο από μία ντετερμινιστική μηχανή Turing για το πρόβλημα του καθορισμού αν μία μηχανή Boolean είναι ικανοποιήσιμη. Το θεώρημα ονομάστηκε από τον (Stephen Cook) και τον (Leonid Levin). Μία σημαντική συνέπεια του θεωρήματος είναι ότι αν υπήρχε ένας ντετερμινιστικός πολυωνυμικός αλγοριθμικός χρόνος για την ικανοποιητική λύση του Boolean,τότε θα υπήρχε ένας ντετερμινιστικός πολυωνυμικός αλγοριθμικός χρόνος για την λύση όλων των προβλημάτων στο . Crucially,το ίδιο ακολουθεί για οποιοδήποτε πρόβλημα. Το ερώτημα για το αν υπάρχει τέτοιος αλγόριθμος καλείτε και θεωρείτε ευρέως το πιο σημαντικό άλυτο πρόβλημα στην επιστημονική θεωρία των υπολογιστών. (el)
- In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin. An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving Boolean satisfiability, then every NP problem can be solved by a deterministic polynomial-time algorithm. The question of whether such an algorithm for Boolean satisfiability exists is thus equivalent to the P versus NP problem, which is widely considered the most important unsolved problem in theoretical computer science. (en)
- En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures". El teorema fue demostrado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que algunas veces es llamado Teorema de Cook-Levin. (es)
- En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet. Il a été démontré en 1971 par Stephen Cook et, sensiblement au même moment, par Leonid Levin. Ce résultat est important car si on montre qu'il existe un algorithme en temps polynomial pour le problème SAT, alors le problème P = NP est résolu. Par ailleurs, ce résultat permet de montrer la NP-dureté de beaucoup d'autres problèmes, par réduction polynomiale. (fr)
- Dalam teori kompleksitas komputasi, Teorema Cook-levin, dikenal juga sebagai Teorema Cook, adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun 1970 pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori ilmu komputer.Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan namun mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu polinomial). Teorema Cook-Levin atau dikenal juga dengan teorema Cook menyatakan bahwa:Problem satisfiability (SAT) adalah NP-complete Terdapat 2 cara dalam pembuktian untuk teorema ini yaitu: 1.
* SAT adalah NP 2.
* Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomial Langkah - langkah pembuktian:SAT adalah NPSAT adalah NP karena masukan dari nilai Boolean ke variabel boolean memenuhi satisfiablility dari suatu ekspresi yang dapat diverifikasikan dalam waktu polinomial oleh sebuah mesin turing deterministik.contoh: E = (X1 V ¬X1 V X2) Ʌ (X3 V X2 V ¬X1) Ʌ (X1 V X2) Ʌ (X3)dengan memberikan assignment pada variabel X1, X2, X3. SAT adalah suatu ekspresi dalam bentuk CNF dan satisfiable jika menghasilkan nilai True.Misal diberikan nilai:X1 =T, X2 = T, X3 = T, maka ekspresi akan bernilai True. Untuk mengecek suatu problem SAT dengan memberikan nilai pada variabel, dapat diselesaikan dalam waktu polinomial, sehingga SAT adalah NP. Setiap problem NP dapat direduksi menjadi SAT dalam waktu polinomialdapat dinyatakan dalam bentuk sebagai berikut: pict1Akan diperlihatkan bahwa untuk setiap A ∈ NP dengan input w, sangat dimungkinkan untuk menghasilkan sebuah formula Boolean yag satisfiable jika w anggota A.
* Ide pembuktian:
* Untuk setiap A adalah NP, dengan input w, menghasilkan sebuah formula boolean φ yang mensimulasikan mesin turing menghasilkan A pada input w.
* Lakukan pengecekan apakah formula boolean yang dihasilkan satisfiable. Ide tersebut dapat diilustrasikan pada gambar dibawah ini
* Pembuktian:
* Asumsi:w : inputA : languageN : mesin turing NP yang menentukan AN menentukan w∈anggota A dalan nk langkah untuk constanta k
* Sebuah variable dapat dinyatakan dalam Xi,j,s
* Xi,j,s: true jika cell [i,j] bernilai s; selain itu bernilai false
* cell[i,j]: cell dengan lokasi baris ke-i dan kolom ke -j
* Suatu Tableau tanpa aturan tertentu dapat berisi konfigurasi yang invalid, misal: cell berisi multiple symbols, tidak dimulai dengan input w dan state q0, konfigurasi neighbour tidak berkorespondensi dengan aturan transisi, dan sebagainya. Sehingga harus dihasilkan formula Boolean yang memaksa tableau agar valid dan menghasilkan result pada accet state.
* Sebuah cell dapat berisi tepat 1 symbol di antara sebuah state, sebuah alphabet tape, dan sebuah #. (φ cell)
* Konfigurasi pertama harus berhubungan dengan input w dan state awal q. (φ start)
* Sebuah konfigurasi diturunkan dari konfigurasi sebelumnya sesuai dengan aturan transisi pada mesin turing. (φmove)
* Harus terdapat sebuah cell berisi accept state. (φaccept)
* Formula:
*
* φcell: terlihat setiap cell berisi paling tidak 1 symbol, dan setiap cell berisi tidak lebih dari 1 simbol yang berbeda.
*
* φstart: terlihat setiap cell dari baris pertama memiliki sebah symbol yang berkorespondensi dengan konfigurasi awal dimana input adalah w.
*
* φaccept: minimal 1 cell merupakan accept state
*
* φmove mengecek apakah setiap window 2x3 adalah legal sesuai dengan aturan transisi dari mesin turing.
*
* Ketika Si,j adalah kumpulan window legal(i,j), dan Ui,j adalah kumpulan dari semua window (i,j), maka:
*
* sehingga kumpulan dari window legal adalah finite.
* Jika φ satisfiable, maka
*
* Karena A dapat direduksi menjadi problem SAT dengan input w, dan SAT adalah problem NP, maka terbukti bahwa SAT adalah NP-complete. (in)
- Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.Il matematico sovietico Leonid Levin arrivò per primo alla dimostrazione del teorema, ma l'articolo con la dimostrazione venne tradotto in inglese anni dopo la pubblicazione di "Complessità delle Procedure di Dimostrazione dei Teoremi". Perciò questo teorema è noto anche come teorema di Cook-Levin poiché entrambi i matematici arrivarono indipendentemente alla dimostrazione del teorema. (it)
- 쿡-레빈 정리(Cook-Levin theorem)는 충족 가능성 문제(SAT)가 NP-완전이라는 것을 증명하는 정리로, 모든 NP 복잡도에 속하는 결정 문제는 다항 시간 내에 충족 가능성 문제로 환산할 수 있다는 것을 의미한다.스티븐 쿡과 레오니드 레빈의 이름을 따서 지어졌다. (ko)
- Twierdzenie Cooka-Levina – jedno z najważniejszych twierdzeń teorii złożoności obliczeniowej. Podaje ono pierwszy znany problem NP-zupełny. Od momentu jego udowodnienia można było stosować do dowodzenia NP-zupełności innych problemów decyzyjnych. (pl)
- Теорема Кука — Левина (также просто теорема Кука) утверждает, что задача о выполнимости булевой формулы в КНФ (SAT) является NP-полной. Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным. В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач следующим образом. Задача принадлежит классу NP, если: 1.
* решением задачи является один из двух ответов: «да» или «нет»; 2.
* требуемый ответ может быть получен на недетерминированном вычислительном устройстве за полиномиальное время. Этот класс, как позже показал Р. Карп (R. Karp) в свою очередь содержит в себе другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые в пределах этого класса одна к другой. После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач. (ru)
- Na teoria da complexidade computacional, o teorema de Cook-Levin, também conhecido como teorema de Cook, afirma que o problema de satisfatibilidade booleana é NP-completo. Isto é, qualquer problema em NP pode ser reduzido em tempo polinomial por uma máquina de Turing determinística para o problema de determinar se uma fórmula booleana é satisfatível. Uma importante consequência desse teorema é que se existe um algoritmo de tempo polinomial para resolver a satisfatibilidade, então existe um algoritmo de tempo polinomial para resolver todos os problemas em NP. Crucialmente, o mesmo acontece para qualquer problema NP-completo. A questão de se tal algoritmo existe é chamada de o Problema P versus NP e esse é amplamente considerado o mais importante problema sem solução da teoria da computação. O teorema é atribuído a Stephen Cook e Leonid Levin. (pt)
- Теорема Кука — Левіна (також просто теорема Кука ) стверджує, що задача здійсненності бульових формул у КНФ (коротше, SAT) є NP — повною. Доведення цієї теореми, отримане Стівеном Куком у його фундаментальній роботі в 1971 році, стало одним з перших найважливіших результатів теорії NP-повних задач. Незалежно в той же час ця теорема була доведена радянським математиком Леонідом Левіним. У доведенні теореми Кука кожна задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач наступним чином. Задача належить класу NP, якщо : 1.
* Розв'язком задачі є одна з двох відповідей: «так» чи «ні» ; 2.
* Потрібна відповідь може бути отримана на недетермінірованому обчислювальному пристрої за поліноміальний час. Цей клас, як пізніше показав Річард Карп, у свою чергу містить у собі інший широкий клас задач, названий Карпом NP-повні задачі, або NPC, — задачі, які зводяться в межах цього класу одна до одної. Після появи результатів Кука була доведена NP-повнота для безлічі інших завдань. При цьому найчастіше для доказу NP-повноти деякої задачі наводиться поліноміальне зведення задачі SAT до даної задачі, можливо в кілька кроків, тобто з використанням декількох проміжних задач. (uk)
- Cook–Levin理論或者Cook理論是有关計算複雜度理論的一个定理。它證明了布尔可满足性问题（SAT 问题）是NP完全問題。即： 1.
* 「一個布尔方程式是否存在解」这个问题本身是一个NP問題； 2.
* 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題。 Cook–Levin理論是以史提芬·古克和為名。 這理論一個非常重要的推论为：如果SAT问题可在多项式时间内被一确定型演算法解决，則所有的NP問題都存在可在多项式时间内解决之的确定型演算法。因此，有關以上這個演算法存在與否的問題等价于P/NP問題——现代的理論電腦科學中最重要的未解問題之一。 (zh)
|
| rdfs:comment
|
- مبرهنة كوك ليفين في نظرية التعقيد الحسابي تنص على أن مسألة الاكتفاء (SAT) هي NP كاملة، يعني أنَّ كل مسألة في NP يمكن اختصارها بوقت حدودي بواسطة آلة تيورنج قطعية حدودية لمسألة تحديد إذا ما صيغة بوليانية قابلة للاكتفاء . أحد تبعات هذه المُبرهنة أنه لو وُجدت خوارزمية لحل مسألة الاكتفاء حينها كل لغة في NP يمكن أيضا حلها كذلك بواسطة نفس الخوارزمية وبوقت حدودي والامر ذاته أيضا لكل لغة تابعة ل- NP كاملة . ايجاد هذه الخوارزمية أو برهان عدم وجودها كان الموضوع الاساسي في علم الحاسوب منذ 30 عام وهذه المسألة تسمى مسألة P=NP . هذه المبرهنة سميت على اسم . (ar)
- En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: Cook demostró este teorema en su artículo de 1971 "The Complexity of Theorem Proving Procedures". El teorema fue demostrado independientemente por Leonid Levin aproximadamente en la misma fecha, por lo que algunas veces es llamado Teorema de Cook-Levin. (es)
- Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.Il matematico sovietico Leonid Levin arrivò per primo alla dimostrazione del teorema, ma l'articolo con la dimostrazione venne tradotto in inglese anni dopo la pubblicazione di "Complessità delle Procedure di Dimostrazione dei Teoremi". Perciò questo teorema è noto anche come teorema di Cook-Levin poiché entrambi i matematici arrivarono indipendentemente alla dimostrazione del teorema. (it)
- 쿡-레빈 정리(Cook-Levin theorem)는 충족 가능성 문제(SAT)가 NP-완전이라는 것을 증명하는 정리로, 모든 NP 복잡도에 속하는 결정 문제는 다항 시간 내에 충족 가능성 문제로 환산할 수 있다는 것을 의미한다.스티븐 쿡과 레오니드 레빈의 이름을 따서 지어졌다. (ko)
- Twierdzenie Cooka-Levina – jedno z najważniejszych twierdzeń teorii złożoności obliczeniowej. Podaje ono pierwszy znany problem NP-zupełny. Od momentu jego udowodnienia można było stosować do dowodzenia NP-zupełności innych problemów decyzyjnych. (pl)
- Cook–Levin理論或者Cook理論是有关計算複雜度理論的一个定理。它證明了布尔可满足性问题（SAT 问题）是NP完全問題。即： 1.
* 「一個布尔方程式是否存在解」这个问题本身是一个NP問題； 2.
* 任何其他NP问题都可以在多項式時間內被一决定型圖靈機歸約成這個問題。 Cook–Levin理論是以史提芬·古克和為名。 這理論一個非常重要的推论为：如果SAT问题可在多项式时间内被一确定型演算法解决，則所有的NP問題都存在可在多项式时间内解决之的确定型演算法。因此，有關以上這個演算法存在與否的問題等价于P/NP問題——现代的理論電腦科學中最重要的未解問題之一。 (zh)
- Στην θεωρία πολυπλοκότητας το θεώρημα Κουκ-Λέβιν (Cook-Levin), το οποίο επίσης είναι γνωστό ως θεώρημα του Κουκ, αναφέρει ότι το είναι NP-πλήρες.Α υτό σημαίνει ότι οποιοδήποτε πρόβλημα στο μπορεί να μειωθεί σε πολυωνυμικό χρόνο από μία ντετερμινιστική μηχανή Turing για το πρόβλημα του καθορισμού αν μία μηχανή Boolean είναι ικανοποιήσιμη. Το θεώρημα ονομάστηκε από τον (Stephen Cook) και τον (Leonid Levin). Το ερώτημα για το αν υπάρχει τέτοιος αλγόριθμος καλείτε και θεωρείτε ευρέως το πιο σημαντικό άλυτο πρόβλημα στην επιστημονική θεωρία των υπολογιστών. (el)
- In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem. The theorem is named after Stephen Cook and Leonid Levin. (en)
- Der kanadische Wissenschaftler Stephen A. Cook begründete 1971 eine neue Klasse von Problemen in der Komplexitätstheorie. Er zeigte, dass eine Teilmenge der Klasse NP existiert, auf die sich alle Probleme aus NP reduzieren lassen. Diese Teilmenge ist damit repräsentativ für die Schwierigkeit von NP und wird als NP-vollständig (NPC für englisch NP complete) bezeichnet. Der nach ihm benannte Satz von Cook sagt aus, dass das Erfüllbarkeitsproblem der Aussagenlogik (SAT, v. engl. satisfiability) NP-vollständig ist. Einen vergleichbaren Satz veröffentlichte Leonid Levin unabhängig von Cook im Jahre 1973, deswegen spricht man manchmal auch vom Satz von Cook und Levin. (de)
- En informatique théorique, plus précisément en théorie de la complexité, le théorème de Cook aussi appelé théorème de Cook-Levin est le théorème qui affirme que le problème SAT, c'est-à-dire le problème de satisfaisabilité d'une formule de la logique propositionnelle, est NP-complet. Il a été démontré en 1971 par Stephen Cook et, sensiblement au même moment, par Leonid Levin. (fr)
- Dalam teori kompleksitas komputasi, Teorema Cook-levin, dikenal juga sebagai Teorema Cook, adalah suatu teori kompleksitas yang dicetuskan oleh Stephen Cook pada Tahun 1970 pada seminar nya, dengan judul "The Complexity of Theorem Prooving Procedures". Paper ini memperkenalkan teori NP-completeness yang hingga sekarang menjadi pusat dari teori ilmu komputer.Teori NP-Completeness ini menyediakan suatu cara untuk mengkategorikan persoalan komputasi yang sulit dengan batas waktu, yaitu jumlah maksimal langkah -langkah yang diperlukan untuk menyelesaikan suatu masalah. Pada paper nya, Cook memaparkan fakta bahwa cukup banyak permasalahan yang sulit untuk diselesaikan namun mudah untuk diverifikasi kebenarannya pada kelas P (dalam waktu polinomial). (in)
- Na teoria da complexidade computacional, o teorema de Cook-Levin, também conhecido como teorema de Cook, afirma que o problema de satisfatibilidade booleana é NP-completo. Isto é, qualquer problema em NP pode ser reduzido em tempo polinomial por uma máquina de Turing determinística para o problema de determinar se uma fórmula booleana é satisfatível. A questão de se tal algoritmo existe é chamada de o Problema P versus NP e esse é amplamente considerado o mais importante problema sem solução da teoria da computação. O teorema é atribuído a Stephen Cook e Leonid Levin. (pt)
- Теорема Кука — Левина (также просто теорема Кука) утверждает, что задача о выполнимости булевой формулы в КНФ (SAT) является NP-полной. Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным. В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач следующим образом. Задача принадлежит классу NP, если: (ru)
- Теорема Кука — Левіна (також просто теорема Кука ) стверджує, що задача здійсненності бульових формул у КНФ (коротше, SAT) є NP — повною. Доведення цієї теореми, отримане Стівеном Куком у його фундаментальній роботі в 1971 році, стало одним з перших найважливіших результатів теорії NP-повних задач. Незалежно в той же час ця теорема була доведена радянським математиком Леонідом Левіним. У доведенні теореми Кука кожна задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач наступним чином. Задача належить класу NP, якщо : (uk)
|
