| 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)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)