Теорема Кука — Левіна

Теорема Кука — Левіна (також просто теорема Кука ) стверджує, що задача здійсненності бульових формул у КНФ (коротше, SAT) є NP — повною.

Доведення цієї теореми, отримане Стівеном Куком у його фундаментальній роботі в 1971 році, стало одним з перших найважливіших результатів теорії NP-повних задач. Незалежно в той же час ця теорема була доведена радянським математиком Леонідом Левіним.

У доведенні теореми Кука кожна задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач розпізнавання властивостей наступним чином. Задача належить класу NP, якщо :

  1. Розв'язком задачі є одна з двох відповідей: «так» чи «ні» (задача розпізнавання властивостей) ;
  2. Потрібна відповідь може бути отримана на недетермінірованому обчислювальному пристрої за поліноміальний час.

Цей клас, як пізніше показав Річард Карп, у свою чергу містить у собі інший широкий клас задач, названий Карпом NP-повні задачі, або NPC, — задачі, які зводяться в межах цього класу одна до одної.

Після появи результатів Кука була доведена NP-повнота для безлічі інших завдань. При цьому найчастіше для доказу NP-повноти деякої задачі наводиться поліноміальне зведення задачі SAT до даної задачі, можливо в кілька кроків, тобто з використанням декількох проміжних задач.

Посилання

Read other articles:

Ghede Chokra's

Ghede Chokra'sAlbum studio karya Shark MoveDirilis1973GenreRockDurasi34:34LabelShark Move RecordsProduserBhagu RamchandKronologi Shark Move Ghede Chokra's(1973) My Life(1976)My Life1976 Ghede Chokra's adalah album perdana dari grup musik Shark Move yang dirilis pada tahun 1973 secara independen[1] oleh Shark Move Records. Album Ghede Chokra's ditempatkan pada peringkat ke-94 dalam daftar 150 Album Indonesia Terbaik versi majalah Rolling Stone Indonesia yang diterbitkan pada edisi ...

 

Bakti Buddhis

Bakti Buddhis adalah salah satu bagian praktik terpenting dalam agama Buddha.[1] Menurut juru bicara Sasana Council of Burma, bakti kepada praktik spiritual Buddhis menginspirasi bakti kepada Tiga Permata, yaitu Buddha, Dhamma atau Dharma, dan Sangha.[2] Banyak umat Buddha memanfaatkan ritual dalam praktik aspirasi spiritual mereka.[3] Contoh praktik bakti membungkuk/namakāra: kepada Buddharūpaṁ, dan di Mahayana juga kepada para Buddha dan bodhisattva lainnya; kepa...

 

Rekayasa biomedis

Pencitraan ultrasonik yang memperlihatkan kandung kemih membutuhkan pemahaman di bidang keteknikan dan kedokteran. Rekayasa biomedis (Inggris: biomedical engineeringcode: en is deprecated /BME) adalah pengaplikasian teknik dan prinsip teknik dalam bidang medis, disebut juga teknik biomedis. Bidang ini menggabungkan kemampuan desain dan pemecahan masalah seorang insinyur dengan ilmu medis dan ilmu biologi di bidang kedokteran, seperti diagnosis, pengawasan, dan terapi.[1] Hampir serupa...

Henry Cabot Lodge

Halaman ini berisi artikel tentang politikus AS Henry Cabot Lodge (1850–1924). Untuk cucunya, (1902–1985), lihat Henry Cabot Lodge Jr. Henry Cabot Lodge Henry Cabot Lodge (12 Mei 1850 – 9 November 1924) adalah seorang anggota Kongres dari Partai Republik dan sejarawan asal Massachusetts. Seorang anggota keluarga Lodge, ia meraih gelar PhD dalam bidang sejarah dari Harvard University. Pranala luar Wikiquote memiliki koleksi kutipan yang berkaitan dengan: Henry Cabot Lodge. ...

 

AnimaNaturalis

AnimaNaturalisFoundedMarch 2003; 21 years ago (2003-03)FocusAnimal rightsArea served Spain and Latin AmericaMethodEducation and activismWebsitewww.animanaturalis.org/en AnimaNaturalis demonstration against the sale of animals in La Rambla, Barcelona AnimaNaturalis is an international non profit animal rights organization whose mission is to Establish, promote and protect the rights of all animals in Spain and Latin America. These rights include the right to life, libert...

 

Georg Dertinger

German politician (1902–1968) Georg DertingerForeign Minister of the GDRIn office11 October 1949 – 15 January 1953Preceded bynew officeSucceeded byAnton Ackermann Personal detailsBorn(1902-12-25)25 December 1902Berlin, Imperial GermanyDied21 January 1968(1968-01-21) (aged 65)Political partyCDUProfessionJournalist Georg Dertinger (25 December 1902 – 21 January 1968) was a German politician. He was born in Berlin into a middle-class Protestant family. Dertinger briefly studi...

بول فايراباند

بول فايراباند (بالألمانية: Paul Karl Feyerabend)‏    معلومات شخصية الميلاد 13 يناير 1924 [1][2][3][4][5][6][7]  فيينا[8]  الوفاة 11 فبراير 1994 (70 سنة) [9][10][3][4][6][11][12]  سبب الوفاة سرطان الدماغ  [لغات أخرى]‏  مواطنة ا�...

 

Prva crnogorska fudbalska liga 2016-2017

Prva crnogorska liga 2016-2017T-Com 1.CFL 2016-2017 Competizione Prva crnogorska liga Sport Calcio Edizione 13ª Organizzatore FSCG Date dal 6 agosto 2016al 27 maggio 2017 Luogo  Montenegro Partecipanti 12 Formula Girone all'italiana A/R/A Risultati Vincitore Budućnost(3º titolo) Retrocessioni Jedinstvo Bijelo PoljeLovćenBokelj Statistiche Miglior marcatore Zoran Petrović (14 reti) Incontri disputati 198 Gol segnati 401 (2,03 per incontro) Cronologia della competiz...

 

Avambraccio

Le informazioni riportate non sono consigli medici e potrebbero non essere accurate. I contenuti hanno solo fine illustrativo e non sostituiscono il parere medico: leggi le avvertenze. Avambraccio umano, tra gomito e polso L'avambraccio è la parte dell'arto superiore compresa tra il gomito e il polso. Il termine è usato in anatomia per distinguerlo dal braccio, parte compresa tra la spalla e il gomito. Indice 1 Anatomia 1.1 Ossa 1.2 Articolazioni 1.3 Muscoli 1.4 Nervi 1.5 Vasi sanguigni 1....

George P. Lawrence

American politician This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: George P. Lawrence – news · newspapers · books · scholar · JSTOR (June 2009) (Learn how and when to remove this message) George Pelton LawrenceGeorge P. Lawrence circa 1908[1]Member of the U.S. House of Representativesfro...

 

Copa dos Campeões 2001

Copa dos Campeões 2001 Competizione Copa dos Campeões Sport Calcio Edizione 2ª Organizzatore CBF Date dal 5 giugno 2001all'11 luglio 2001 Luogo  Brasile Partecipanti 9 Risultati Vincitore  Flamengo(1º titolo) Secondo  San Paolo Statistiche Miglior marcatore Luís Fabiano (San Paolo), 7 gol Incontri disputati 17 Gol segnati 61 (3,59 per incontro) Cronologia della competizione 2000 2002 Manuale La Copa dos Campeões 2001 (in italiano Coppa dei Campioni 2001) è...

 

Deçan Municipality

Municipality in District of Gjakova, KosovoDeçan MunicipalityMunicipalityKomuna e DeçanitOpština Dečani / Општина Дечани FlagSealLocation of the municipality of Deçan within KosovoCoordinates: 42°32′N 20°17′E / 42.533°N 20.283°E / 42.533; 20.283CountryKosovoDistrictDistrict of GjakovaGovernment • MayorBashkim RamosajArea • Municipality297 km2 (115 sq mi) • Rank20th in KosovoElevation550 m...

List of historical markers of the Philippines in Metro Manila

This article has an unclear citation style. The reason given is: Citations need to use a consistent format. The references used may be made clearer with a different or consistent style of citation and footnoting. (February 2024) (Learn how and when to remove this message) Historical marker for the Rizal Monument This list of historical markers installed by the National Historical Commission of the Philippines (NHCP) in Metro Manila is an annotated list of people, places, or events in the reg...

 

الحزب العربي الديمقراطي

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (فبراير 2016) الحزب العربي الديمقراطي البلد لبنان  التأسيس تاريخ التأسيس 1974  المؤسسون علي عيد قائد الحزب رفعت علي...

 

Mayer Carl von Rothschild

German Jewish banker and politician Mayer Carl Freiherr von RothschildMayer Carl von Rothschild, date unknownBorn(1820-08-05)5 August 1820Naples[1]Died16 October 1886(1886-10-16) (aged 66)NationalityGermanOccupationBankerSpouseLouise von RothschildChildren Adèle von Rothschild [de]Emma Louise von RothschildThérèse von RothschildHannah Luise von Rothschild [de]Margaretha Alexandrine von RothschildBertha Clara von Rothschild Parent(s)Carl Mayer von Roth...

Eagle Peak (Modoc County, California)

Mountain in the state of California Eagle PeakHighest pointElevation9,897 ft (3,017 m) NAVD 88[1]Prominence4,352 ft (1,326 m)[2]ListingCalifornia county high points 15thNorth America isolated peaks 151stCoordinates41°17′00″N 120°12′03″W / 41.283441436°N 120.200754167°W / 41.283441436; -120.200754167[1]GeographyEagle PeakLocation in California LocationModoc County, California, U.S.Parent rangeWarner ...

 

Burmese python

Species of large, nonvenomous snake Burmese python Conservation status Vulnerable  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Reptilia Order: Squamata Suborder: Serpentes Family: Pythonidae Genus: Python Species: P. bivittatus Binomial name Python bivittatus(Kuhl, 1820) Native distribution in green Synonyms[2] Python molurus bivittatus Kuhl, 1820 The Burmese python (Python bivittatus) is one of the largest spec...

 

Killing of Muhammad al-Durrah

2000 shooting of a Palestinian boy in the Gaza Strip Killing of Muhammad al-DurrahMuhammad (left) and Jamal al-Durrah (right) filmed by Talal Abu Rahma for France 2Date30 September 2000; 23 years ago (2000-09-30)Timec. 15:00 Israel Summer Time (12:00 UTC)LocationNetzarim junction, Gaza StripCoordinates31°27′53″N 34°25′38″E / 31.46472°N 34.42722°E / 31.46472; 34.42722First reporterCharles Enderlin for France 2Filmed byTalal Abu R...

إشارات المرور في الولايات المتحدة

غلاف طبعة 2009 لوثيقة MUTCD الصادرة من إدارة الطرق السيارة الفيدرالي (FHWA) التابع لوزارة النقل الأمريكية في الولايات المتحدة، علامات الطرق في معظمها موحدة من قبل الأنظمة الاتحادية. ويخص الأمر بالذكر دليل الموحد لأجهزة التحكم المرورية (MUTCD)، والدليل المرافق له الخاص بالطرق السري...

 

Innovation Place Research Park

Saskatchewan Opportunities Corporation (doing business as Innovation Place)Company typeCrown corporationIndustryProperty ManagementHeadquartersSaskatoon, Saskatchewan, CanadaNumber of locations3 (2011)Number of employees142 [1][full citation needed]Websitewww.innovationplace.com Innovation Place is the registered business name of the Saskatchewan Opportunities Corporation (SOCO), a crown corporation in Saskatchewan.[2] SOCO operates two research parks: one located near...