NP (Complexitat)

En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic. Equivalentment, aquest és el conjunt de problemes els quals la seva solució es pot "verificar" per una màquina de Turing determinista en temps polinòmic.[1][2]

Introducció i aplicacions

La importància d'aquesta classe de problemes de decisió és que conté força problemes interessants de cerca i optimització, dels quals es vol saber si existeix una solució per un problema donat.

Com a exemple senzill, considerar el problema de determinar si un nombre n és nombre compost. Per nombres molt grans, és un problema força complex per resoldre'l eficientment; l'aproximació més simple requereix un temps exponencial en log n, el nombre de bits d'entrada. Per altra banda, un cop hem trobat un candidat per ser el factor de n, la següent funció respon si el candidat és un factor o no: 

booleà ésFactorNoTrivial(n, d)
si n és divisible per d i
d ≠ 1 i d ≠ n
retorna cert
si no
retorna fals

si n és compost, aquesta funció retornarà cert per alguna entrada d. Si n és primer, aquesta funció sempre retorna fals, sigui quin sigui el valor d. Tots els problemes NP tenen una funció determinista com aquesta, que retorna cert només quan es dona una entrada i la prova de què l'entrada és en el llenguatge. La solució és verificable en temps polinòmic. En aquesta màquina se li diu verificador del problema.

Si es té una màquina no determinista, provar si nombre és compost o no és senzill. Es pot dividir en n branques diferents, en O(log n) passes; després, cada una d'aquestes branques criden la funció ésFactorNoTrivial(n, d) per un d. Si alguna té èxit, el nombre és compost; si no, és primer.

Per tant, la dificultat dels problemes NP és trobar la resposta de forma eficient, donada una forma eficient (en temps polinòmic) de verificar-la un cop trobada.

Altres problemes en 'NP són:

Referències

  1. ↑ Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. ↑ Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529. 

Read other articles:

Pulung Siswantara

Pulung SiswantaraLahirPulung Siswantara24 April 1982 (umur 41)Jombang, Jawa Timur, IndonesiaPekerjaanDosen, Pelawak tunggalTahun aktif2012—sekarang Pulung Siswantara S.KM, M.Kes (lahir 24 April 1982) adalah seorang dosen dan pelawak tunggal berkebangsaan Indonesia. Pulung tercatat sebagai dosen di Fakultas Kesehatan Masyarakat Universitas Airlangga.[1] Selain itu, Pulung adalah salah satu kontestan Stand Up Comedy Indonesia Kompas TV[2] musim ke-3 (SUCI 3) pada ta...

 

Firman

Royal mandate or decree issued by a sovereign in an Islamic state For the surname, see Firman (surname). Ferman redirects here. For the surname or given name, see Ferman (name). A Fat'h Ali Shah Qajar firman in Shikasta Nastaʿlīq script, January 1831 Look up firman in Wiktionary, the free dictionary. A firman (Persian: فرمان, romanized: farmân; Turkish: ferman),[1] at the constitutional level, was a royal mandate or decree issued by a sovereign in an Islamic state. During...

 

Gifted (film)

GiftedPoster rilis bioskopSutradaraMarc WebbProduser Karen Lunder *Andy Cohen Ditulis olehTom FlynnPemeran Chris Evans * Mckenna Grace * Lindsay Duncan * Jenny Slate * Octavia Spencer Penata musikRob SimonsenSinematograferStuart DryburghPenyuntingBill PankowPerusahaanproduksi FilmNation Entertainment * Grade A Entertainment DistributorSearchlight PicturesTanggal rilis 12 April 2017 (2017-04-12) (United States) NegaraUnited StatesBahasaEnglish Gifted adalah film Amerika Serikat ...

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年 大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍 中華民國政党 中國國民黨获奖 青天白日勳章（追贈）军事背景效忠 中華民國服役 國民革命軍 中華民國陸軍服役时间1924年－1958年军衔 二級上將 （追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

 

List of acts of the Parliament of the United Kingdom from 1999

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

 

كأس السوبر الإيطالي 1990

1990 Supercoppa Italianaالحدثكأس السوبر الإيطالي Napoli Juventus الدوري الإيطالي كأس إيطاليا 5 1 التاريخ1 September 1990الملعبملعب دييغو أرماندو مارادونا (إيطاليا)، نابولي, ItalyالحكمCarlo Longhiالحضور62,404 → 1989 1991 ← مارادونا شارك في المبارة كأس السوبر الإيطالي Supercoppa Italiana 1990 هي بطولة كرة قدم قبل بداية الم�...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

Hexacorallia

Class of cnidarians with 6-fold symmetry HexacoralliaTemporal range: Fortunian–Present[1] PreꞒ Ꞓ O S D C P T J K Pg N A stony coral, Acropora latistella Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Cnidaria Subphylum: Anthozoa Class: HexacoralliaHaeckel, 1896 Orders See text. Aspidiscus cristatus from the Cenomanian (Upper Cretaceous) of southern Israel; oral view. Aspidiscus cristatus from the Cenomanian (Upper Cretaceous) of southern Israel; aboral vie...

 

Aircraft maintenance technician

Profession and licensed qualification The examples and perspective in this article may not represent a worldwide view of the subject. You may improve this article, discuss the issue on the talk page, or create a new article, as appropriate. (December 2010) (Learn how and when to remove this message) Technicians work on the mechanisms underneath a wing. An aircraft mechanic, aviation mechanic or aircraft maintenance technician (AMT) is a tradesperson who carries out aircraft maintenance and re...

RAMiCS

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) 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: RAMiCS – news · newspapers · books · scholar · JSTOR (July 2022) (Learn how and when to remove this message...

 

E (Cyrillic)

Letter of the Cyrillic script For the letter E (E e) of the Bulgarian, Macedonian, Serbian and Ukrainian alphabets, see Ye (Cyrillic). Cyrillic letter Cyrillic letter EPhonetic usage:[e], [ɛ]The Cyrillic scriptSlavic lettersАА̀А̂А̄ӒБВГҐДЂЃЕЀЕ̄Е̂ЁЄЖЗЗ́ЅИІЇꙆЍИ̂ӢЙЈКЛЉМНЊОО̀О̂ŌӦПРСС́ТЋЌУУ̀У̂ӮЎӰФХЦЧЏШЩꙎЪЪ̀ЫЬѢЭЮЮ̀ЯЯ̀Non-Slavic lettersӐА̊А̃Ӓ̄ӔӘӘ́Ә̃ӚВ̌ԜГ̑Г̇Г̣Г̌Г̂Г̆Г̈г̊ҔҒӺҒ̌...

 

Бур-де-Бигор

КоммунаБур-де-БигорBourg-de-Bigorre Герб 43°05′29″ с. ш. 0°15′40″ в. д.HGЯO Страна  Франция Регион Юг — Пиренеи Департамент Верхние Пиренеи Кантон Ланнемезан Мэр Режин Сарра(2014—2020) История и география Площадь 7,92 км² Высота центра 331–574 м Часовой пояс UTC+1:00, летом UTC+2:00 Насе...

NGC 4211

NGC 4211   الكوكبة الهلبة[1]  رمز الفهرس NGC 4211 (الفهرس العام الجديد)KPG 327a (Catalogue of isolated pairs of galaxies in the northern hemisphere)UGC 7277 (فهرس أوبسالا العام)PGC 39221 (فهرس المجرات الرئيسية)2MASX J12153585+2810396 (Two Micron All-Sky Survey, Extended source catalogue)MCG+05-29-042 (فهرس المجرات الموروفولوجي)NGC 4211A (الفهرس العام الجديد)NGC ...

 

Monte Paramont

Questa voce sugli argomenti montagne d'Italia e Valle d'Aosta è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti dei progetti di riferimento 1, 2. Monte ParamontStato Italia Regione Valle d'Aosta Altezza3 301 m s.l.m. CatenaAlpi Coordinate45°40′19.24″N 7°01′45.26″E45°40′19.24″N, 7°01′45.26″E Mappa di localizzazioneMonte Paramont Dati SOIUSAGrande ParteAlpi Occidentali Grande SettoreAlpi Nord-oc...

 

Shantilal Shah Engineering College

This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Shantilal Shah Engineering College – news · newspapers · books · scholar · JSTOR (September 2024) (Learn how and when to remove this message)Shantilal Shah Engineering CollegeTypePublicEstablished3 April 1983; 41 years ago (1983-04-03)AccreditationAICTEGovernment of GujaratChancellorDr. ...

フルーツポンチ

「フルーツポンチ」のその他の用法については「フルーツポンチ (曖昧さ回避)」をご覧ください。 いろいろなパンチ フルーツポンチ、フルーツパンチ（英: fruit punch）は、果汁等を混ぜたアルコール飲料「パンチ」（ポンチ酒、ポンチ）に、切った果物（フルーツ）を入れた飲み物・デザート。今ではアルコールを含まないものもある。 概要 スペイン王家のバカラ�...

 

Krieg gegen den Terror

Collage aus Bildern des Krieges gegen den Terror:oben links: die Ruinen des World Trade Centers nach den Anschlägen vom 11. September 2001,oben rechts: US-Soldaten mit einer Boeing C-17 Globemaster in Afghanistan,unten links: eine Bombe explodiert nahe einem US-Konvoi bei Bagdad,unten rechts: US-Soldaten im Gefecht in Afghanistan. Krieg gegen den Terror (englisch War on Terror) oder Krieg gegen den Terrorismus (englisch War on Terrorism bzw. Global War on Terrorism, kurz GWOT) war ein v...

 

Virtus Kleb Ragusa

Virtus Kleb RagusaPallacanestro Segni distintiviUniformi di gara Casa Trasferta Colori sociali Azzurro Dati societariCittàRagusa Nazione Italia ConfederazioneFIBA Europe FederazioneFIP CampionatoSerie B Nazionale Fondazione1948 Scioglimento2006 Rifondazione2006 DenominazioneVirtus Ragusa (1948-2006)Nova Virtus Ragusa (2006-2020)Virtus Kleb Ragusa (2020-) PresidenteSabrina Sabbatini AllenatoreGianni Recupido ImpiantoPalaPadua(2,000 posti) Sito webwww.virtusragusabasket.it/ La Virtus Kleb...

جوسيب سكوبلار

جوسيب سكوبلار (بالكرواتية: Josip Skoblar)‏  معلومات شخصية الميلاد 12 مارس 1941 (العمر 83 سنة)[1] الطول 1.77 م (5 قدم 9 1⁄2 بوصة)[2][2] مركز اللعب مهاجم الجنسية كرواتيا  معلومات النادي النادي الحالي أولمبيك مارسيليا (كشاف) مسيرة الشباب سنوات فريق 1956–1958[3] ناد�...

 

Bezinghem

Bezinghem La mairie. Blason Administration Pays France Région Hauts-de-France Département Pas-de-Calais Arrondissement Montreuil Intercommunalité CC du Haut Pays du Montreuillois Maire Mandat Philippe Ducrocq 2020-2026 Code postal 62650 Code commune 62127 Démographie Gentilé Bezinghemois Populationmunicipale 379 hab. (2021 ) Densité 29 hab./km2 Géographie Coordonnées 50° 35′ 42″ nord, 1° 49′ 37″ est Altitude Min. 50 mMax. 176...