Reducción (complejidad)

Ejemplo de reducción de un problema de satisfacibilidad booleana a un problema de cobertura de vértices. Los vértices azules forman una cobertura que se corresponde con los valores verdaderos.

En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas.

Intuitivamente, un problema es reducible a un problema si las soluciones de existen y dan una solución para siempre que tenga solución. Así, resolver no puede ser más difícil que resolver . Normalmente, esto se expresa de la forma , y se añade un subíndice en para indicar el tipo de reducción utilizada. Por ejemplo, se usa la letra como subíndice para indicar que la reducción puede realizarse en tiempo polinomial: .


Véase también

Read other articles:

Murders of William and Patricia Wycherley

1998 double murder case Photo of William Wycherley released by police during their investigation. At some point over the Early May bank holiday weekend in 1998, William and Patricia Wycherley were shot and killed in their home in a suburb of Mansfield, England, by their daughter Susan and her husband, Christopher Edwards. The Edwards then buried the bodies in the garden behind the house and went on to use the Wycherleys' identities to commit various acts of fraud intended to fund their hobby ...

 

Kakap singkek

Kakap singkek Status konservasi Risiko Rendah (IUCN 3.1)[1] Klasifikasi ilmiah Domain: Eukaryota Kerajaan: Animalia Filum: Chordata Kelas: Actinopterygii Ordo: Perciformes Famili: Lutjanidae Genus: SymphorusGünther, 1872 Spesies: Symphorus nematophorusBleeker, 1860 Sinonim[2][3] Genus: Glabrilutjanus Fowler, 1931 Paradicichthys Whitley, 1930 Spesies: Mesoprion nematophorus Bleeker, 1860 Glabrilutjanus nematophorus (Bleeker, 1860) Lutjanus nematophorus (Bleeker, ...

 

Guyana

Artikel ini bukan mengenai Guinea. Untuk kegunaan lain, lihat Guyana (disambiguasi). Republik Kooperatif GuyanaCooperative Republic of Guyana (Inggris) Bendera Lambang Semboyan: One People, One Nation, One Destiny (Indonesia: Satu Rakyat, Satu Bangsa, Satu Tujuan)Lagu kebangsaan: Dear Land of Guyana, of Rivers and Plains(Indonesia: Tanah Guyana yang Terhormat, Sungai dan Dataran)Ibu kota(dan kota terbesar)Georgetown6°48′21″N 58°9′3″W / 6.80583°N 58.15083°...

Semenanjung Tasman

Letak Semenanjung Tasman di Tasmania tenggara. Semenanjung Tasman adalah semenanjung yang terletak di Tasmania tenggara, Australia, kurang lebih 75 km dari Hobart. Semenanjung Tasman terletak di sebelah selatan dan barat Semenanjung Forestier. Kedua semenanjung ini dihubungkan oleh tanah genting yang disebut Eaglehawk Neck, sementara tanah genting yang disebut East Bay Neck menghubungkan kedua semenanjung tersebut dengan pulau Tasmania. Semenanjung Tasman dikelilingi oleh perairan: Teluk...

 

Masjid Faisal

Masjid Faisalفیصل مسجدMasjid Faisal, masjid terbesar sekaligus masjid nasional PakistanAgamaAfiliasiIslamCabang/tradisiSunni IslamLokasiLokasiIslamabadPakistanLokasi di PakistanKoordinat33°43′48″N 73°02′18″E / 33.729944°N 73.038436°E / 33.729944; 73.038436Koordinat: 33°43′48″N 73°02′18″E / 33.729944°N 73.038436°E / 33.729944; 73.038436ArsitekturArsitekVedat DalokayTipeMasjidGaya arsitekturIslam kontemporerDidirika...

 

Palace of the Fans

Former baseball park in Cincinnati, Ohio USA Palace of the FansLeague Park IIIFormer namesLeague Park (1884–1901)LocationFindlay St. & McLean Ave., Cincinnati, OhioCoordinates39°7′1″N 84°32′12″W / 39.11694°N 84.53667°W / 39.11694; -84.53667Capacity6,000Field sizeLeft Field - 360 ft (109.7 m)[1]Left-Center - 418 ft (127.4 m)Center Field - 400 ft (121.9 m)Right-Center - 375 ft (114.3 m)Right Field - 450 ft (137.2 m)SurfaceGrassConstructionBroke ...

Sammy Wilson (politician)

Northern Irish DUP politician The Right HonourableSammy WilsonMPOfficial portrait, 2017Democratic Unionist Party Chief Whip in the House of CommonsIn office17 December 2019 – 23 February 2024LeaderJeffrey DonaldsonPreceded byJeffrey DonaldsonMinister of Finance and PersonnelIn office1 July 2009 – 29 July 2013First MinisterPeter RobinsonPreceded byNigel DoddsSucceeded bySimon HamiltonMinister of the EnvironmentIn office9 June 2008 – 1 July 2009First MinisterPet...

 

New England town

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: New England town – news · newspapers · books · scholar · JSTOR (May 2023) (Learn how and when to remove this message) Unit of government in New England, US TownAlso known as:New England town This map shows the six New England states and their local political su...

 

Brad Halliday

English footballer (born 1995) Brad Halliday Halliday playing for York City in 2015Personal informationFull name Bradley Halliday[1]Date of birth (1995-07-10) 10 July 1995 (age 28)[2]Place of birth Redcar, EnglandHeight 5 ft 11 in (1.80 m)[3]Position(s) Defender / MidfielderTeam informationCurrent team Bradford CityNumber 2Youth career2000–2010 Redcar Town2010–2013 Middlesbrough2013 Newcastle United2013–2014 MiddlesbroughSenior career*Years Te...

Stasiun Jordan

Jordan佐敦Stasiun angkutan cepat MTRNama TionghoaTionghoa 佐敦 Hanyu PinyinZuǒdūnYale KantonJódēun TranskripsiTionghoa StandarHanyu PinyinZuǒdūnYue: KantonRomanisasi YaleJódēunJyutpingZo2deon1 Informasi umumLokasiNathan Road × Jordan Road, Kwun ChungDistrik Yau Tsim Mong, Hong KongKoordinat22°18′18″N 114°10′18″E / 22.3049°N 114.1718°E / 22.3049; 114.1718Koordinat: 22°18′18″N 114°10′18″E / 22.3049°N 114.1718°E...

 

List of revolvers

Overview of revolving cylinder handguns This is a list of single- and double-action revolvers, listed alphabetically by manufacturer. This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by adding missing items with reliable sources. The table is sortable for every column. Name Manufacturer Image Cartridge Chambers Country Production date ALFA Steel Revolvers ALFA - PROJ spol. s r.o. .22 WMR (2330, 2331, 2341, 2361, 2363 Sport).22 LR (233...

 

Galactic astronomy

Study of the Milky Way galaxy and its contents An artist's conception of the Milky Way Galactic astronomy is the study of the Milky Way galaxy and all its contents. This is in contrast to extragalactic astronomy, which is the study of everything outside our galaxy, including all other galaxies. Galactic astronomy should not be confused with galaxy formation and evolution, which is the general study of galaxies, their formation, structure, components, dynamics, interactions, and the range of f...

Jason Liebrecht

American voice actor Jason LiebrechtLiebrecht at GalaxyCon Raleigh in 2021BornErnesto Jason LiebrechtOccupationVoice actorYears active1986–present Ernesto Jason Liebrecht[1] is an American voice actor who voices for a number of English versions of Japanese anime series and video games. Some of his major roles include Lavi and the Millennium Earl in the D.Gray-man series, Tapion in Dragon Ball Z: Wrath of the Dragon, Syaoran in Tsubasa: Reservoir Chronicle and Cardcaptor Sakura:...

 

Serangan Prusia Timur

Serangan Prusia TimurBagian dari Front Timur pada Perang Dunia IIPara prajurit dari Tentara ke-4 Jerman di perbatasan Prusia Timur sebelum serangan tersebutTanggal13 Januari – 25 April 1945LokasiPrusia TimurHasil Kemenangan SovietPihak terlibat  Jerman  Uni SovietTokoh dan pemimpin Georg-Hans ReinhardtFriedrich HossbachFriedrich-Wilhelm MüllerErhard RausWalter WeissDietrich von Saucken Konstantin RokossovskyIvan Chernyakhovsky †Aleksandr VasilevskyHovhannes BagramyanKekuat...

 

Fletcher Pratt

American military historian and fantasy writer Fletcher PrattFletcher Pratt, as pictured in the June 1929 issue of Science Wonder StoriesBorn(1897-04-25)April 25, 1897Buffalo, New YorkDiedJune 10, 1956(1956-06-10) (aged 59)Long Branch, New Jersey, USPen nameIrvin Lester, George U. FletcherOccupationNovelist, historianNationalityAmericanGenreScience fiction, fantasy, historyNotable worksOrdeal by Fire Murray Fletcher Pratt (25 April 1897 – 10 June 1956) was an American writer of history...

Cape Coral, Florida

Kota Cape Coral, FloridaKotaCape Coral and Fort Myers dari udara, Juli 1997Julukan: The Cape, Canal CityLokasi di Lee County dan negara bagian FloridaNegara Amerika SerikatNegara bagian FloridaCounty LeeDidirikan1957Incorporated1970Pemerintahan • JenisCouncil-Manager • City ManagerGary King • Distrik 1Kenneth McClain • Distrik 2Peter Brandt • Distrik 3William Deile • Distrik 4Chris Chulakes-LeetzLuas&#...

 

Bulwer, Queensland

Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) Town in Queensland, AustraliaBulwerQueenslandOne of the scuttled ships on the beach at Bulwer, 2011BulwerCoordinates27°04′43″S 153°22′11″E / 27.0786°S 153.3697°E / -27.0786; 153.3697 (Bulwer (town centre))Population59 (2021 census)[1] • Density148/km2 (380/sq mi)Postcode(s)4025Area...

 

Plato Bolaven

15°N 106°E / 15°N 106°E / 15; 106 Air terjun Tad Fane Tad Lo Truk penebangan kayu. Juni 2009 Pengolahan kopi di Dataran Tinggi Bolaven Plato Bolaven adalah wilayah dataran tinggi di selatan Laos. Sebagian besar dataran tinggi terletak di dalam Provinsi Champasak Laos, meskipun ujung dataran tinggi juga terletak di Salavan, Sekong dan Provinsi Attapeu. Dataran tinggi ini terletak di antara Deretan Annam, yang membentang di sepanjang perbatasan timur Laos dengan Viet...

Chaperon (Kopfbedeckung)

Junger Mann mit Chaperon, Gemälde von Sandro Botticelli Philipp der Gute mit Chaperon, Gemälde von Rogier van der Weyden Jan van Eyck: Mann mit blauem Chaperon. Der Chaperon (aus dem Französischen, [ʃapˈʀɔ̃]) ist eine Kopfbedeckung, die im Mittelalter von Frauen und Männern getragen wurde und aus einer Kapuze mit langer, herabhängender Spitze, der Gugel, hervorging. Chaperon rouge steht im Französischen für Rotkäppchen. Auch nannte man im 19. Jahrhundert ältere Personen Chaperon...

 

Tierra Amarilla

Tierra Amarilla Comuna Escudo Ubicación de Tierra Amarilla en la Región de Atacama.Coordenadas 27°28′00″S 70°16′00″O / -27.466666666667, -70.266666666667Entidad Comuna • País  Chile • Región Atacama • Provincia Copiapó • Circunscripción IV - Atacama • Distrito N.º 4Alcalde Cristóbal Zúñiga Arancibia (PCCh)Eventos históricos   • Fundación 22 de diciembre de 1891 (132 años)Superficie   • ...