Machine de Blum-Shub-Smale

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources ().

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Page d’aide sur l’homonymie

Pour les articles homonymes, voir BSS.

Une machine de Blum-Shub-Smale (ou machine BSS ou real RAM) est un modèle de calcul utilisé en informatique théorique, en particulier en calculs en nombres réels. Ce genre de machine calcule sur les nombres réels (autrement dit, son alphabet de bande est ). Elle manipule les réels comme des entités atomiques (c'est-à-dire sans s'intéresser à leur structure interne) et les opérations et tests qu'elle peut réaliser en temps unitaire correspondent respectivement aux fonctions et aux relations dont on dispose sur . Ce modèle a été proposé par Stephen Smale, Michael Shub et Lenore Blum en 1989[1].

En pratique, on ne munit pas les machines BSS de toutes les opérations possibles sur les réels. Au contraire, on s'intéresse généralement à des structures comme où les deux opérations possibles sont l'addition et l'opposition, et où seuls des tests d'égalité sont possibles.

Intérêt des machines BSS

Les machines BSS fournissent un véritable modèle de calcul sur les nombres réels, où l'on ne se soucie pas des problèmes d'arrondi dus à la précision limitée des représentations booléennes que manipulent, par exemple, les machines de Turing « traditionnelles ». Mais le modèle de Blum, Shub et Smale ouvre également de nouvelles perspectives d'approche du problème P = NP dans la mesure où, sur certaines structures de , le problème «  ? » est équivalent au problème standard[Quoi ?].

Voir aussi

Liens externes

Notes et références

  1. ↑ (en) Stephen Smale, Michael Shub et Lenore Blum, « On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines », Bulletin of the AMS, vol. 21, no 1,‎ , p. 1-46.

Read other articles:

Franz Gruber

Franz Xaver GruberPotret oleh Sebastian Stief (Hallein,1846), Silent Night Museum, HalleinLahir25 November 1787Hochburg-Ach, Austria Hulu, Monarki HabsburgMeninggal7 Juni 1863 (aged 75)Hallein, Salzburg, Kekaisaran AustriaPekerjaanTeacherchurch organistcomposerKaryaStille Nacht (Malam Kudus) Franz Xaver Gruber (25 November 1787 – 7 Juni 1863) adalah seorang guru SD Austria dan pemain orgen di gereja yang bersama dengan Josef Mohr menulis lagu Silent Night (Stille Nacht dalam ...

 

Mårten Eskil Winge

Winge, dalam Svenskt porträttgalleri [sv] Mårten Eskil Winge (21 September 1825 – 22 April 1896) adalah seorang seniman asal Swedia. Ia adalah profesor di Akademi Kesenian Kerajaan Swedia. Ia diasosiasikan dengan mazhab lukisan Düsseldorf. Keseniannya dipengaruhi oleh tema-tema mitologi Nordik yang juga ditemukan dalam karya-karya buatan Nils Blommér (1816–1853) dan Carl Wahlbom (1810-1858).[1][2] Referensi ^ Mårten Eskil Winge (1825-1896). ...

 

Edward Brittain

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 November 2020. Edward BrittainMCNama lahirEdward Harold BrittainLahir(1895-11-30)30 November 1895Macclesfield, Cheshire, InggrisMeninggal15 Juni 1918(1918-06-15) (umur 22)Piave, Asiago, ItaliaDikebumikanPemakaman Inggris Granezza, Italia (45°48′28″N 11°31...

God of War: Ascension

God of War God of War: Ascension (atau dalam bahasa Polandia God of War: Wstapienie; dalam bahasa Rusia God of War: Восхождение; atau sinonimnya God of War IV[1]) adalah permainan yang dibuat oleh Santa Monica Studios dan dipublikasikan oleh Sony Computer Entertainment Architect (SCEA) bertajuk orang ketiga Petualangan-Aksi (Third Person Adventure-Action) dengan konten untuk Dewasa 17 tahun ke atas (Mature). God of War: Ascension rilis pertama kali di Playstation 3 (PS3) pa...

 

SMA Negeri 81 Jakarta

SMA Negeri 81 JakartaInformasiDidirikan21 Januari 1986JenisNegeriAkreditasiAKepala SekolahDr. Joko Arwanto, M.Pd.[1]Jumlah kelas24 kelas RegulerJurusan atau peminatanMIPA dan IPSRentang kelasX, XI, XII MIPA, XII IPSKurikulumKurikulum Merdeka dan Kurikulum 2013Jumlah siswasekitar 900 siswa (36-40 siswa per kelas)AlamatLokasiJl. Kartika Eka Paksi, KPAD Jatiwaringin, Cipinang Melayu, Makasar, Jakarta Timur, Jakarta Timur, DKI Jakarta, IndonesiaTel./Faks.021-8629940 / 021-8...

 

Dita Fakhrana

Dita FakhranaLahirDita Fakhrana Utami11 Mei 1994 (umur 29)Bandung, Jawa Barat, IndonesiaKebangsaanIndonesiaAlmamaterUniversitas Pelita HarapanPekerjaanPembawa acaraPenyanyiTahun aktif2017 - sekarangDikenal atasMalam Malam dan Candaan Ruang TengahSuami/istriIlham Prawira ​ ​(m. 2020; c. 2021)​ Rino Yosiaki ​(m. 2022)​Anak1 Pemenang kontes kecantikanGelarPuteri Indonesia DKI Jakarta 2 2017Warna rambutHitamWa...

Rumah pistol

Rumah senjata sederhana di kawasan Bayou St. John, New Orleans setelah Angin ribut Katrina. Rumah-rumah pistol terdiri dari tiga sampai lima kamar. Rumah pitol di kawasan Fifth Ward, Houston, Texas, pada 1973, diambil dalam sebuah foto oleh Danny Lyon. Rumah pistol (Inggris: shotgun house) adalah sebuah kediaman domestik empat persegi sempit, yang biasanya panjangnya tak lebih dari sekitar 12 kaki (3.5 m), dengan kamar-kamar saling membelakangi satu sama lain dan pintu di setiap...

 

Ben Smith (ice hockey, born 1988)

American professional ice hockey player (born 1988) Not to be confused with Ben Smith (ice hockey coach). Ice hockey player Ben Smith Smith with the EHC München in May 2022Born (1988-07-11) July 11, 1988 (age 35)Winston-Salem, North Carolina, U.S.Height 5 ft 11 in (180 cm)Weight 198 lb (90 kg; 14 st 2 lb)Position Right wingShoots RightDEL teamFormer teams EHC MünchenChicago BlackhawksSan Jose SharksToronto Maple LeafsColorado AvalancheAdler MannheimR�...

 

Белоглазый виреон

Белоглазый виреон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:П�...

Unión Balompédica Conquense

Unión Balompédica ConquenseCalcio Segni distintivi Uniformi di gara Casa Trasferta Colori sociali Bianco, nero Dati societari Città Cuenca Nazione  Spagna Confederazione UEFA Federazione FEF Fondazione 1946 Presidente Carlos Lacort Allenatore Eloy Jiménez Stadio Stadio La Fuensanta(3.500 posti) Sito web www.ubconquense.es Palmarès Si invita a seguire il modello di voce L'Unión Balompédica Conquense è una società calcistica con sede a Cuenca, in Castiglia-La Mancia, in Spagna. G...

 

Pakistan Cycling Federation

Pakistan Cycling Federationپاکستان سائیکلنگ فیڈریشنSportCycle racing/Track ChampionshipsCategoryCycling sportsJurisdictionNationalMembership9AbbreviationPCFFounded1947; 77 years ago (1947)AffiliationUnion Cycliste InternationaleRegional affiliationAsian Cycling ConfederationHeadquartersLavish Building 471, Saddar Road, Peshawar Cantt, PakistanPresidentSyed Azhar Ali ShahSecretaryM Haroon GeneralOfficial websitewww.pcf.com.pk The Pakistan Cycling Federa...

 

Compressive strength

Capacity of a material or structure to withstand loads tending to reduce size 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: Compressive strength – news · newspapers · books · scholar · JSTOR (May 2014) (Learn how and when to remove this message) Measuring the compressive strength of a steel drum In mechani...

Autriche-Hongrie

Monarchie austro-hongroise(de) Österreichisch-Ungarische Monarchie (hu) Osztrák–Magyar Monarchia 30 mars 1867 – 31 octobre 1918(51 ans, 7 mois et 1 jour) Armoiries de l'Autriche-HongrieHaut : 1915-1918Bas : 1867-1915Pas de drapeau officiel (voir drapeaux de l'Autriche-Hongrie). Devise en latin : Indivisibiliter ac inseparabiliter (« Indivisibles et inséparables ») Hymne Gott erhalte L'Autriche-Hongrie en 1914. Inf...

 

土库曼斯坦总统

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府（Oguzkhan Presidential Palace）機關所在地阿什哈巴德任命者直接选举任期7年，可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關（英语：National Council of Turkmenistan） ...

 

Matthew Shepard and James Byrd Jr. Hate Crimes Prevention Act

American hate crime legislation Matthew Shepard and James Byrd Jr. Hate Crimes Prevention ActOther short titlesLocal Law Enforcement Hate Crimes Prevention Act of 2009Long titleTo provide Federal assistance to States, local jurisdictions, and Indian tribes to prosecute hate crimes, and for other purposes.Enacted bythe 111th United States CongressAnnounced inthe 111th United States CongressNumber of co-sponsors120CodificationTitles amended18 U.S.C.: Crimes and Criminal ProcedureU.S.C...

Tayo Tarmadi

Tayo Tarmadi Panglima Kodam III/SiliwangiMasa jabatan1995–1997PendahuluMayjen TNI Muzani SyukurPenggantiMayjen TNI Djamari Chaniago Informasi pribadiLahir17 Maret 1943 (umur 81)Karawang, Jawa BaratAnakBrigjen TNI. Bagus Suryadi TayoTempat tinggalCihanjuang 12A/Perum Katumiri, Kec. Parongpong, Kab. Bandung BaratAlma materAMN (1966)Karier militerPihak IndonesiaDinas/cabang TNI Angkatan DaratMasa dinas1966 – 1997Pangkat Mayor Jenderal TNINRP20740SatuanInfanteriSunting kotak in...

 

Subinfeudation

Feudal practice English feudalismHarold Sacramentum Fecit Willelmo Duci(Bayeux Tapestry) FiefEcclesiastical fiefCrown landAllodial titleAppanageVassalFeoffmentSeignorySubinfeudationFeoffeeFealtyHomageAffinityFeudal maintenanceFeudal fragmentationBastard feudalismLivery Manorialism Lord of the manorManorial courtManor house (List)DemesneGlebeOverlordLordPeasantSerfdomFree tenant Feudal land tenure in England Land tenureEnglish feudal baronyFeudal baronKnight's feeKnight-serviceBaronagePeerageS...

 

Lerna

Tangga menuju lantai atas pada Awal Helladik Wangsa Tiles Lerna[1] (bahasa Yunani: Λέρνη) adalah sebuah wilayah mata air dan bekas danau dekat pantai timur Peloponnesos, selatan Argos. Situsnya dekat desa Mili di Teluk Argolik paling terkenal sebagai sarang Hidra, ular air berkepala banyak khthonik, makhluk sangat kuno saat Herakles membunuhnya, sebagai pembantu kedua Herakles Mata air karst yang kuat masih ada; sedangkan danaunya, berkurang ke laguna lumpur pada abad ke-19 t...

Airport/Facility Directory

The Airport/Facility Directory (abbreviated A/FD), now identified as Chart Supplement in the U.S., is a pilot's manual that provides comprehensive information on airports, large and small, and other aviation facilities and procedures. Description The directory is published in seven volumes that cover the continental United States, Puerto Rico, and the U.S. Virgin Islands. Each volume is updated every 56 days by the United States Department of Transportation (DOT) with information from the Fed...

 

Edmontosaurus

Edmontosaurus Periode Zaman Kapur Akhir, 73–66 jtyl PreЄ Є O S D C P T J K Pg N Kerangka E. regalis di Oxford University Museum of Natural HistoryTaksonomiFilumChordataKelasReptiliaOrdoOrnithischiaFamiliHadrosauridaeGenusEdmontosaurus Lambe, 1917 Tipe taksonomi†Edmontosaurus regalisLambe, 1917 Tata namaSinonim takson AnatosaurusLull & Wright, 1942 AnatotitanChapman & Brett-Surman, 1990 Claosaurus annectens Marsh, 1892 UgrunaalukMori et al., 2015[1] Spesies lain †E...