Зведення (теорія складності обчислень)

Зведення в теорії складності обчислень — перетворення однієї задачі до іншої. У загальному випадку, для алгоритму, що перетворює примірники задачі на примірники задачі , які мають ту саму відповідь («так» або «ні»), кажуть, що зводиться до , таким чином, звідність — це відношення між двома задачами. За допомогою такого зв'язку можна доводити обчислюваність задачі або її належність до того чи іншого класу складності.

Деякі види зведень: зведення за Куком, зведення за Карпом, зведення за Левіном, зведення за Тюрінгом[en].

Зведення за Тюрінгом — найзагальніша форма зведення: деякий алгоритм (обчисле́нний на машині Тюрінга) можна викликати будь-яку кількість разів, при цьому кожен виклик буде вважатися одним кроком алгоритму; для формального визначення звідності за Тюрінгом використовується поняття тюрінг-машини з оракулом.

Джерела

  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
  • Роджерс Х.(інші мови). Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
  • Курс «Вступ до структурної теорії складності» (рос.)

Read other articles:

Daniel Sedin

Daniel Sedin Daniel saat praktik pada Maret 2012 Lahir 26 September 1980 (umur 43)Örnsköldsvik, Swedia Tinggi 185 m (606 ft 11 in) Berat 85 kg (187 pon; 13 st 5 pon) Posisi Sayap Kiri Shoots Kiri NHL teamFormer teams Vancouver CanucksModo Hockey (SEL) Tim nasional  Swedia NHL Draft 2nd overall, 1999Vancouver Canucks Karier bermain 1997–sekarang Daniel Sedin (kelahiran 26 September 1980) adalah seorang pemain sayap hoki es profesional Swedi...

 

Chun Ho-jin

Ini adalah nama Korea; marganya adalah Chun. Chun Ho-jinHojin Chun OCN Original 'Save Me 2' Production Presentation 2019Lahir9 September 1960 (umur 63)Busan, Korea SelatanPendidikanUniversitas Inha - Chemistry (dropped out)PekerjaanAktorTahun aktif1983-sekarangAgenJ,Wide-CompanySuami/istri(m. 1986)Orang tuaChun Gyu-deok (ayah)Nama KoreaHangul천호진 Hanja千虎珍 Alih AksaraCheon Ho-jinMcCune–ReischauerCh'ŏn Ho-chin Chun Ho-jin (Hangul: 천호진; lahir 9 September 19...

 

دورة الأكسجين

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

Penny

2 pence 1797. Britania Raya, George III. Tembaga. Penny (jamak pence) adalah sebuah koin (jamak pennies) atau satuan mata uang (jamak pence) yang digunakan di beberapa negara berbahasa Inggris. Penny biasanya merupakan denominasi terkecil dalam sistem mata uang. Nilai ⅟100 pound sterling Britania, pound Irlandia yang sudah tidak digunakan, pound Gibraltar, pound Santa Helena, pound Kepulauan Falkland. ⅟240 pound sterling Britania atau Irlandia sebelum desimalisasi pada 15 Februari 1971, p...

 

Food Network

Food NetworkDiluncurkan23 November 1993; 30 tahun lalu (1993-11-23)PemilikTelevision Food Network, G.P.(Warner Bros. Discovery [69%],Nexstar Media Group [31%])Pangsa pemirsaUK:0.18%0.02% (+1) (September 2015 (2015-09), BARB)SloganDig InNegaraAmerika SerikatKantor pusatNew York City, New York, Amerika SerikatSaluran seindukCooking ChannelDIY NetworkGACHGTVTravel ChannelSitus webfoodnetwork.comTelevisi InternetTVPlayerWatch live (hanya di UK)PlayStation VueInternet Protocol television...

 

Federal Reserve Reform Act of 1977

Federal Reserve Reform Act of 1977Long titleAn Act to extend the authority for the flexible regulation of interest rates on deposits and accounts in depository institutions, to promote the accountability of the Federal Reserve System, and for other purposes.Enacted bythe 95th United States CongressEffectiveNovember 16, 1977CitationsPublic lawPub. L.Tooltip Public Law (United States) 95–188Statutes at Large91 Stat. 1387CodificationActs amendedFederal Reserve Act Bank Hold...

Shirley MacLaine

American actress, and author (born 1934) Shirley MacLaineMacLaine in 1960BornShirley MacLean Beaty (1934-04-24) April 24, 1934 (age 90)Richmond, Virginia, U.S.OccupationsActressauthoractivistdancersingerYears active1951–presentSpouse Steve Parker ​ ​(m. 1954; div. 1982)​ChildrenSachi ParkerRelativesWarren Beatty (brother)AwardsFull listWebsiteshirleymaclaine.com Shirley MacLaine (born Shirley MacLean Beaty on April 24, 1934)[1 ...

 

P. N. Dhar

Prithvi Nath Dhar Masa jabatan1970–2012 Informasi pribadiLahir(1919-03-01)1 Maret 1919[1]Jammu dan KashmirMeninggal19 Juli 2012(2012-07-19) (umur 93)New Delhi, IndiaSuami/istriSheila DharAlma materKolese Hindu, Universitas DelhiSunting kotak info • L • B Prithvi Nath Dhar (P.N. Dhar, 1 Maret 1919 – 19 Juli 2012) adalah seorang ekonom dan kepala sekretariat Indira Gandhi dan salah satu penasehat terdekatnya.[2] Kehidupan awal dan karier P. N...

 

Harry's Bar (Venice)

Restaurant in Venice, Italy Sign for Harry's Bar Harry's Bar is a restaurant located at Calle Vallaresso 1323, Venice, Italy, owned by Cipriani S.A. History Harry's Bar was opened in 1931 by Giuseppe Cipriani. According to the company's history, Harry Pickering, a rich young American, had been frequenting the Hotel Europa in Venice, where Cipriani was a bartender. When Pickering suddenly stopped coming to the hotel bar, Cipriani asked him why. Pickering explained that he was broke because his...

Dream High 2

2012 South Korean TV series Dream High 2Promotional posterHangul드림하이 2Revised RomanizationDeurimhai 2McCune–ReischauerTŭrimhai 2 Genre Music Teen Comedy Drama Romance Written by Heo Sung-hye (Ep. 1–6) Jang Eun-mi (Ep. 7–16) Directed by Lee Eung-bok Mo Wan-il Creative directors Bae Yong-joon J.Y. Park Starring Kang So-ra Jeong Jin-woon Jay B Park Ji-yeon Hyolyn Park Seo-joon Country of originSouth KoreaOriginal languageKoreanNo. of seasons2No. of episodes16ProductionExecutive pr...

 

Bruce Vilanch

American comedy writer, head writer for the Oscars Bruce VilanchBruce Vilanch in 2012BornBruce Gerald Vilanch (1948-11-23) November 23, 1948 (age 75)New York City, New YorkOccupations Writer songwriter actor Years active1974–present Bruce Gerald Vilanch (born November 23, 1948) is an American comedy writer, songwriter and actor.[1] He is a two-time Emmy Award-winner. Vilanch is best known to the public for his four-year stint on Hollywood Squares, as a celebrity participan...

 

Гайанский доллар

Гайанский доллар[a] англ. Guyana Dollar[b] фр. Dollar de Guyane[b] Вышедшие из обращения 10 долларов100 долларов 1976 года Коды и символы Коды ISO 4217 GYD (328) Символы G$, GY$ и GY$ Аббревиатуры $ • GY$ Территория обращения Страна-эмитент  Гайана Производные и параллельные ед�...

Laut Greenland

Laut GreenlandGunung es laut GreenlandLaut GreenlandLetakAmerika Utara dan Eropa UtaraKoordinat76°N 8°W / 76°N 8°W / 76; -8Koordinat: 76°N 8°W / 76°N 8°W / 76; -8Jenis perairanLautTerletak di negaraGreenland, Islandia, dan NorwegiaArea permukaan1.205.000 km2 (465.300 sq mi)Kedalaman rata-rata1.444 m (4.738 ft)Kedalaman maksimal4.846 m (15.899 ft)Volume air1.747.250 km3 (419.000 cu mi)Liha...

 

David Dunn (Maine politician)

American politician (1811–1894) David DunnDunn in 184618th Governor of MaineIn officeJanuary 1, 1844 – January 3, 1844Preceded byEdward KavanaghSucceeded byHugh J. AndersonMember of the Maine House of RepresentativesIn office1840–1844 Personal detailsBorn(1811-01-17)January 17, 1811Cornish, Massachusetts(now Maine)DiedFebruary 17, 1894(1894-02-17) (aged 83)Mechanic Falls, MainePolitical partyDemocratic David Dunn (January 17, 1811 – February 17, 1894) wa...

 

Banjir India 2009

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Februari 2023. Banjir India 2009 menimpa beberapa negara bagian di India pada Juli 2009, menewaskan sekitar 36 orang di Orissa dan 13 di Kerala. Negara bagian yang paling terpengaruh oleh banjir ini meliputi Orissa,[1][2][3][4] Kerala...

Jalan Tol Payakumbuh–Pangkalan

Jalan Tol Payakumbuh-PangkalanPayakumbuh-Pangkalan Toll RoadJalan Tol PakalanInformasi ruteBagian dari Jalan Tol Trans SumateraDikelola oleh BUJT (Dalam Proses)Panjang:46 km (29 mi)Berdiri:Tahap 1 (TBA)Tahap 2 (TBA)Tahap 3 (TBA) – sekarangPersimpangan besarUjung Barat: Jalan Tol Bukittinggi - Payakumbuh Simpang Susun PayakumbuhSimpang Susun HarauSimpang Susun PangkalanUjung Timur: Jalan Tol Bangkinang Pangkalan Tahap 3LetakKota besar:PayakumbuhHarauPangkalanSistem jalan ...

 

A' Katīgoria 2010-2011

Voce principale: A' Katīgoria (calcio). A' Katīgoria 2010-2011 Competizione A' Katīgoria Sport Calcio Edizione 72ª Organizzatore CFA Date dal 27 agosto 2010all'11 maggio 2011 Luogo  Cipro Partecipanti 14 Risultati Vincitore  APOEL(21º titolo) Retrocessioni  APOP Kinyras Doxa Katōkopias AEP Paphos Statistiche Miglior marcatore Miljan Mrdaković (21 gol) Incontri disputati 218 Gol segnati 569 (2,61 per incontro) Cronologia della competizione 2009-20...

 

Associazione Sportiva Messina (1945-1946)

Voce principale: Associazione Calcio Rinascita Messina. AS MessinaCalcio Segni distintiviUniformi di gara Casa Trasferta Colori sociali Bianco, giallo, rosso Dati societariCittàMessina Nazione Italia ConfederazioneFIFA Federazione FIGC Fondazione1945 Scioglimento1946Presidente Vincenzo Nicotrapoi Giuseppe Gensabella Allenatore Oronzo Pugliese StadioGazzi(~ 25.000 posti) PalmarèsSi invita a seguire il modello di voce L'Associazione Sportiva Messina è stata una società calcistica ital...

鉄道員 (小説)

鉄道員（ぽっぽや）著者 浅田次郎発行日 1997年4月28日発行元 集英社国 日本言語 日本語形態 上製本ページ数 288コード ISBN 978-4-08-774262-6 [ ウィキデータ項目を編集 ]テンプレートを表示 ポータル 文学 『鉄道員』（ぽっぽや）は、浅田次郎の短編小説。『小説すばる』平成7年（1995年）11月号に掲載され、後に同名の短編集にまとめられ、1997年4月に集英社から刊行�...

 

Homonationalism

Nationalist ideology and LGBT people Not to be confused with Queer nationalism. Part of a series onNationalism Nation forming Nationalism in the Middle Ages Anthem Church Colours Emblem Father Flag Epic God Identity Language Myth Sport State Symbol Treasure Core values Allegiance Independence Patriotism Self-determination Solidarity Types African Anarchist Blind Bourgeois Business Welfare Civic American French Irish Communist Constitutional patriotism Corporate Cyber- Ecological Economic Ethn...