NP-повна задача

NP-повна задача (англ. NP-complete) — в теорії алгоритмів та теорії складності це задача, що належить до класу NP та всі задачі з класу NP можна звести до неї за поліноміальний час.^[1]

Формальне визначення

Нехай $L$ — мова (проблема) що належить до класу NP. Мова $L$ називається NP-повною якщо виконуються такі умови:

$L$ належить до NP.
Для довільної мови $L'$ в NP існує зведення до $L$ за поліноміальний час.^[2]

Якщо довільний окремий випадок задачі $L_{1}$ можна перетворити в деякий окремий випадок задачі $L_{2}$ в такий спосіб, що розв'язок задачі $L_{1}$ можна отримати за поліноміальний час від розв'язку задачі $L_{2}$ то кажуть, що $L_{1}$ зводиться до $L_{2}$ .^[1]

Якщо P ≠ NP, то всі NP-повні проблеми знаходяться в множині NP — P, через це доведення NP-повноти задачі можна розглядати як додатковий аргумент на користь того, що проблема не належить до класу P і для неї не існує точного поліноміального алгоритму.

NP-повнота в сильному сенсі

Задача називається NP-повною в сильному сенсі, якщо у неї існує підзадача, яка:

Не є задачею з числовими параметрами (тобто максимальне значення величин, що зустрічаються в цій задачі, обмежено зверху поліномом від довжини входу),
Належить до класу NP,
Є NP-повною.

Клас таких задач називається NPCS. Якщо гіпотеза P ≠ NP справедлива, то для NPCS задач не існує псевдополіноміального алгоритму.

Гіпотеза P ≠ NP

Рівність класів P і NP вже понад 30 років є відкритою проблемою. Наукове співтовариство схиляється до негативного вирішення цього питання — у цьому випадку за поліноміальний час вирішувати NP-повні задачі не вдасться.

Приклади

Докладніше: Список NP-повних задач

Див. також

Примітки

↑ ^а ^б Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.) . Москва: Мир. с. 442—443.
↑ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2-ге). Addison-Wesley. с. 419. ISBN 0-201-44124-1.

п о р NP-повні задачі
Класифікація	Дослідження операцій:Оптимізація:Комбінаторна оптимізація
Основи	NP-повна задача · Клас складності NP · Клас складності P
Задачі	Задача заміщення сторінок · Задача здійсненності бульових формул · Задача комівояжера · Задача листоноші · Задача пакування рюкзака · Задача про кліку · Задача про точне покриття · Задача про пакування в ємності (двомірне пакування • лінійне пакування тощо) • Задача Штейнера • Задача про вершинне покриття • Задача про незалежну множину • Задача про покриття множини · ...
Теорія складності обчислень	Теорія складності обчислень • Класи складності
Логічні ігри та головоломки	Гра в п'ятнашки (гра в N²-1) (Задача пошуку найкоротшого рішення) • Задачі, рішення яких застосовуються в Тетрисі • Задача узагальненого судоку • Задача про заповнення латинського квадрата • Задачі какуро
Списки	21 NP-повна задача Карпа · Список NP-повних задач
Дослідники	Річард Карп
Див. також	Прикладна математика • Теорія алгоритмів • Динамічне програмування

п о р Класи складності алгоритмів
Вважаються легкими	P L NL AC NC P-повні BQP BPP RP ZPP APX
Припускаються складними	NP co-NP NP-повні NP-складні co-NP-повні UP #P (#P-повні) IP PSPACE (PSPACE-повні) R PP AM MA QMA
Вважаються складними	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME PR RE Co-RE RE-complete Co-RE-complete PH
Ієрархії	Поліноміальна Гжегорчика
Теорія складності обчислень • Список алгоритмів

Це незавершена стаття про програмування.
Ви можете допомогти проєкту, виправивши або дописавши її.

Read other articles:

Kelenjar tiroid

Kelenjar tiroidKelenjar endokrinTiroid dan paratiroidRincianArterisuperior thyroid artery, inferior thyroid artery, thyreoidea ima,accessory thyroid arteries from oesophageal and tracheal branchesVenasuperior thyroid vein, middle thyroid vein, inferior thyroid vein,kocher's vein or 4th thyroid veinSarafsympathetic system middle cervical ganglion, inferior cervical ganglionLimfaprelaryngeal, pretracheal, jugulo-diagastric groups of lymph nodesPengidentifikasiBahasa Latinglandula thyroideaMeSHD...

Sriwijaya University

University in Indonesia Sriwijaya UniversityUniversitas SriwijayaMottoIlmu Alat PengabdianMotto in EnglishEducation as tool for DedicationTypePublicEstablishedOctober 29, 1960[1][2]RectorProf. Dr. Ir. H. Anis Saggaff, MSCE., IPU., ASEAN.Eng.AddressJl. Palembang - Prabumulih Raya KM 32-UNSRI Indralaya, Ogan Ilir, South Sumatra, Indonesia, Indralaya and Palembang, South Sumatra, Indonesia2°59′11″S 104°44′04″E / 2.986444°S 104.734333°E / -...

Perang Armenia-Azerbaijan

Perang Armenia-AzerbaijanBagian dari Perang Dunia I dan Perang Saudara RusiaTanggalMaret 1918-1920LokasiArmenia dan AzerbaijanHasil Permasalahan teritori Karabakh diserahkan pada AzerbaijanPihak terlibat Armenia Republik Demokratik Armenia Nagorno-Karabakh Pemberontak Nagorno-Karabakh Hanya untuk Pertempuran Baku: Britania Raya Kediktatoran Sentrokaspia Azerbaijan SSR Azerbaijan Republik Demokratik Azerbaijan Kesultanan Utsmaniyah Republik Soviet Sosi...

Aldo Corzo

Aldo Corzo Aldo Corzo berlatih bersama tim sepak bola Peru di Piala Dunia 2018.Informasi pribadiNama lengkap Aldo CorzoTanggal lahir 20 Mei 1989 (umur 34)Tempat lahir Lima, PeruTinggi 172 cm (5 ft 8 in)Posisi bermain BekInformasi klubKlub saat ini UniversitarioNomor 29Karier senior*Tahun Tim Tampil (Gol)2017 – Universitario 44 (6)Tim nasional2009 – Peru 25 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Aldo Corzo (lahir 20 Mei 1989) adalah s...

Sakti

Untuk kegunaan lain, lihat Sakti (disambiguasi). Saktienergi surgawiAdi Parashakti Lalita Tripura Sundari duduk di atas Brahma, Wisnu, Rudra, Syiwa and ParasiwaNama lainAdi Parashakti, Dewi, Durga, Mahalakshmi, Parwati, Saraswati, Kali, SatiAfiliasiDewiSenjataSemua Artikel ini adalah bagian dari seriSakta Ketuhanan tertinggi Adi Parasakti (Mahadewi) Perwujudan Mahadewi Lalita Tripura Sundari Tridewi Saraswati Laksmi Durga Navadurga Mahawidya Kali Sati Parwati Bhairawi Kamakhya (Kubjika) Yogin...

Meitei literature

Indian literature Further information: Meitei classical language movement and Meitei linguistic purism movement You can help expand this article with text translated from the corresponding article in Manipuri. Click [show] for important translation instructions. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translat...

Sudbury (provincial electoral district)

Provincial electoral district in Ontario, Canada For the federal electoral district, see Sudbury (federal electoral district). Sudbury Ontario electoral districtProvincial electoral districtLegislatureLegislative Assembly of OntarioMPP Jamie WestNew DemocraticDistrict created1905First contested1908Last contested2022DemographicsPopulation (2016)[1]80,840Electors (2018)67,410Area (km²)158Pop. density (per km²)511.6Census division(s)Greater Sudbury Sudbury is a provin...

Società Sportiva Calcio Napoli 1984-1985

Voce principale: Società Sportiva Calcio Napoli. SSC NapoliStagione 1984-1985 Sport calcio Squadra Napoli Allenatore Rino Marchesi All. in seconda Alberto Delfrati Presidente Corrado Ferlaino Serie A8º Coppa ItaliaOttavi di finale Maggiori presenzeCampionato: Caffarelli, Maradona (30)Totale: Maradona (36) Miglior marcatoreCampionato: Maradona (14)Totale: Maradona (17) StadioSan Paolo Abbonati67 398[1] Maggior numero di spettatori82 890 vs Milan (21 ottobre 1984) Mino...

أتراك

هذه المقالة عن المجموعة العرقية الأتراك وليس عن من يحملون جنسية الجمهورية التركية أتراكTürkler (بالتركية) التعداد الكليالتعداد 70~83 مليون نسمةمناطق الوجود المميزةالبلد القائمة ... تركياألمانياسورياالعراقبلغارياالولايات المتحدةفرنساالمملكة المتحدةهولنداالنمساأسترالي�...

Alinne Moraes

In this Portuguese name, the first or maternal family name is Dorelli de Magalhães and the second or paternal family name is Morais. Brazilian actress Alinne MoraesMoraes in 2012Born (1982-12-22) 22 December 1982 (age 41)Sorocaba, São Paulo, BrazilOccupationActressYears active2002–presentPartner(s)Cauã Reymond (2002–2005) Mauro Lima (2012–present)Children1 Aline Cristine Dorelli de Magalhães e Morais[1] (Portuguese: [aˈlini moˈɾajs]; born 22 December...

جزيرة فوكلاند الشرقية

جزيرة فوكلاند الشرقية الاسم الرسمي (بالإنجليزية: East Falkland)‏ الإحداثيات 51°48′22″S 58°47′14″W / 51.806111111111°S 58.787222222222°W / -51.806111111111; -58.787222222222 [1] تقسيم إداري البلد المملكة المتحدة[2] التقسيم الأعلى جزر فوكلاند خصائص جغرافية المساحة 6605 �...

Bracelet du sexe

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Le fond de cet article sur la sexologie est à vérifier (juillet 2020). Améliorez-le ou discutez des points à vérifier. Si vous venez d’apposer le bandeau, merci d’indiquer ici les points à vérifier. Bracelet jaune. Les bracelets du sexe sont un jeu de bracelets en silicone d'une variété de couleurs, soit une douzaine de bracelets peuvent être portée sur chaque poignet selon les règles du jeu. Il e...

WJOD

Country radio station in Iowa WJODAsbury, IowaBroadcast areaDubuque and VicinityFrequency103.3 MHzBranding103 WJODProgrammingFormatCountryAffiliationsCompass Media NetworksPremiere NetworksOwnershipOwnerTownsquare Media(Townsquare License, LLC)Sister stationsKLYV, KXGE, WDBQ, WDBQ-FMTechnical information[1]Licensing authorityFCCFacility ID34596ClassC3ERP6,600 wattsHAAT196 meters (643 ft)Transmitter coordinates42°24′15.98″N 90°34′12″W / 42.4044389°N 90.5...

Hengyang Metro

Planned metro system in Hengyang, China Hengyang MetroOverviewNative name衡阳轨道交通LocaleHengyang. Hunan, ChinaTransit typeMonorail rapid transitNumber of lines2 (phase 1)Number of stations43 (phase 1)OperationOperation will start2025TechnicalSystem length59.0km (phase 1) Hengyang Metro (Chinese: 衡阳轨道交通; pinyin: Héngyáng Guǐdào Jiāotōng), officially Hengyang Rail Transit, is a planned monorail rapid transit system in Hengyang, Hunan, China. Once completed, th...

Swaar Metaal

2007 studio album by Kobus!Swaar MetaalStudio album by Kobus!Released2007GenreExtreme metal/Heavy MetalLabelRhythm RecordsKobus! chronology 100% Skuldgevoelvry(2004) Swaar Metaal(2007) Swaar Metaal is the third studio album by South African heavy metal band Kobus!, released on the independent record label Rhythm Records in March 2007. The ten-track album (and unlisted hidden track) sees the band's founder-members, Francois Breytenbach Blom and Theo Crous breaking away from the previo...

Francis Marion

American military officer, planter and politician (1732–1795) Francis MarionNickname(s)The Swamp FoxBornc. 1732Berkeley County, South Carolina, British America[1]DiedFebruary 27, 1795(aged c. 63)Berkeley County, South Carolina, U.S.BuriedSt. Stephen, South CarolinaAllegiance Great Britain United StatesService/branch South Carolina Militia Continental ArmyYears of service1757–1782RankLieutenant colonel Continental ArmyBrigadier General South Carolina Milit...

Luqmanulhakim

Ustadz LuqmanulhakimLahir27 Juni 1984 (umur 40)Pontianak, Kalimantan BaratKebangsaanIndonesia AlmamaterUniversitas Darussalam Gontor International Islamic University MalaysiaPekerjaanDa'iUlamaPengasuh Pesantren Ustadz Luqmanulhakim (lahir 27 Juni 1984) adalah Pendiri dan sekaligus Pengasuh Pondok Masjid Munzalan Mubarakan Ashabul Yamin di Kubu Raya, Kalimantan Barat. Ustadz Luqman atau kerap dipanggil Ayah Man juga merupakan salah satu pimpinan di dalam Dewan Pimpinan Masjid Kapal Munza...

Holger Sundström

Swedish sailor (1925–2023) Holger SundströmPersonal informationBorn17 April 1925 (1925-04-17)Gothenburg, SwedenDied9 April 2023 (2023-04-10) (aged 97)Gothenburg, SwedenHeight186 cm (6 ft 1 in)Weight85 kg (187 lb)Sailing careerClubKattegattflottiljen, Gothenburg Medal record Representing Sweden Olympic Games 1964 Tokyo Star class Holger Bertil Sundström (17 April 1925 – 9 April 2023) was a Swedish Olympic sailor.[1] Together with Pell...

Nhà Khwarezm-Shah

Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. Bài này nằm trong loạt bài về Lịch sử Iran Huyền sử Nhà Pishdadi Nhà Kayani Thời kỳ cổ đại Trước Công Nguyên (TCN) Tiền sử Iran Thời cổ đại–4000 Văn hoá Kura–Arax...

Offensive de Qousseir

Pour les articles homonymes, voir Bataille de Qousseir. Bataille de Qousseir Carte des opérations dans la région de Qousseir. Informations générales Date 4 avril - 8 juin 2013 Lieu District de Qousseir Issue Victoire des loyalistes Belligérants Hezbollah République arabe syrienne Iran Armée syrienne libre Front al-Nosra Commandants Qasem Soleimani Mohieddin al-Zain Forces en présence Inconnues Inconnues Pertes Inconnues Inconnues Guerre civile syrienneBatailles Batailles de la guerre...