EXPTIME

En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n.

En términos de DTIME,

Se sabe que

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE

y por el teorema de la jerarquía temporal:

P ⊂ EXPTIME

de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas).

La clase de complejidad EXPTIME-completo es el conjunto de problemas de decisión que están en EXPTIME tales que todo problema de EXPTIME tiene una transformación polinomial hacia cada uno de los problemas de EXPTIME-completo. Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPTIME-completo puede ser visto como el conjunto de los problemas más difíciles de EXPTIME.

Como ejemplos de problemas EXPTIME-completos están el buscar a partir de una posición (en una versión generalizada) del Ajedrez, Damas, o Go y determinar si el primer jugador tiene una secuencia de jugadas ganadora a partir de allí. Estos juegos son EXPTIME-completos dado que las secuencias de jugadas a partir de una configuración dada es exponencial sobre el tamaño del tablero. (Cuando se tiene un juego generalizado en el cual el número de jugadas a partir de una configuración es polinómico en el tamaño del tablero, el mismo problema resulta generalmente PSPACE-completo.)

EXPTIME-completo

Un problema de decisión es EXPTIME-completo si es en EXPTIME, y todos los problemas de EXPTIME tienen tiempo-polinomial, o una reducción de la misma. En otras palabras, hay un algoritmo de tiempo polinómico que transforma los casos de uno a instancias del otro con la misma respuesta. Se podría pensar que los problemas que son EXPTIME-completo son los problemas más difíciles en EXPTIME. Nótese que aunque no sabemos si NP es un subconjunto de P o no, sí sabemos que los problemas EXPTIME-completo no están en P; se ha demostrado que estos problemas no pueden resolverse en tiempo polinomial.

En teoría de la computabilidad, uno de los problemas básicos no decidibles es el de decidir si una máquina de Turing determinista (DTM) se detiene(problema de la parada). Uno de los problemas más fundamentales EXPTIME-completo es una versión más sencilla de ello, que dice si un DTM detiene en a lo sumo k pasos. Es en EXPTIME porque obviamente una de simulación requiere O(k) tiempo, y la entrada k se codifica mediante O(log k) bits. Es EXPTIME-completo, ya que podemos usarlo para determinar si una máquina que resuelve un problema de EXPTIME acepta en forma exponencial el número de pasos; no va a usar más.

Otros ejemplos de problemas EXPTIME-completo incluyen el problema de evaluar una situación generalizada en el ajedrez, damas o Go (con las reglas japonesas ko). Estos juegos pueden ser EXPTIME-completo porque los juegos pueden durar de una serie de movimientos que es exponencial en el tamaño del tablero. En el ejemplo del Go, la regla japonesa del ko es lo suficientemente insoluble para implicar EXPTIME-completo, pero no se sabe si las más flexibles como las americanas o chinas son EXPTIME-completo.

Por el contrario, juegos generalizados que pueden durar una serie de movimientos que son polinómicos en el tamaño del tablero son a menudo PSPACE-completo.

Read other articles:

Bagian riil dan imajiner

Ilustrasi pada bidang kompleks. Bagian riil dari bilangan kompleks z = x + iy adalah x, dan bagian imajinernya adalah y. Dalam matematika, jika diketahui bilangan kompleks z = x + iy (yang mana i adalah bilangan imajiner sedang x dan y adalah bilangan riil) maka x disebut bagian riil dan y disebut bagian imajiner dari z.[1] Bagian riil dari bilangan kompleks z ditulis Re(z) atau ℜ(z) dan bagian imajiner ditulis Im(z) atau ℑ(z), ℜ dan ℑ a...

 

Paulus Diakonus

Penggambaran Paulus Diaconus di dalam sebuah naskah dari abad ke-10 (Laurentian Library Plut. 65.35 fol. 34r) Paulus Diakonus (skt. 720-an – 13 April 799 SM), juga dikenal sebagai Paulus sang Diakon, Warnefridus, Barnefridus, Winfridus dan terkadang dengan akhiran Cassinensis (seperti Monte Cassino), merupakan Ordo Santo Benediktus, Ahli Taurat, dan Sejarawan Lombardia. Kehidupan Konon leluhur yang bernama Leupichis memasuki Italia dengan bimbingan Alboin dan menerima wilayah di atau di dek...

 

Iconoclastia

Segni dell'arte iconoclasta bizantina, nell'abside della chiesa di Santa Irene a Costantinopoli. «Adunche al tempo di Gostantino imperatore et di Silvestro papa sormontò su la fede christiana. Ebbe la ydolatria grandissima persecuzione in modo tale, tutte le statue et le picture furon disfatte et lacerate di tanta nobiltà et anticha et perfetta dignità […] Et per leuare uia ogni anticho costume di ydolatria costruirono i templi tutti essere bianchi. […] Finita che fu l’arte stettero...

Sakurajima

This article is about the volcano. For other uses, see Sakurajima (disambiguation). Stratovolcano in Kagoshima Prefecture, Kyushu, Japan SakurajimaView of Sakurajima from mainland Kagoshima, 2009Highest pointElevation1,117 m (3,665 ft)Coordinates31°34′50″N 130°39′29″E / 31.58056°N 130.65806°E / 31.58056; 130.65806GeographySakurajimaKagoshima Prefecture, JapanShow map of JapanSakurajimaSakurajima (Kagoshima Prefecture)Show map of Kagoshima Pre...

 

BBC Two

BBC TwoCaractéristiquesCréation 21 avril 1964Propriétaire BBCSlogan « Nation shall speak peace unto nation »Langue AnglaisPays Royaume-UniStatut Généraliste nationale publiqueSiège social LondresAncien nom BBC2 (1964-1986)Site web www.bbc.co.uk/bbctwoDiffusionDiffusion Analogique terrestre, numérique terrestre, satellite, câble, ADSL et Webmodifier - modifier le code - modifier Wikidata BBC Two (autrefois BBC2) est la seconde chaîne de télévision britannique diffusée p...

 

Erovnuli Liga 2022

Erovnuli Liga 2022Crystalbet National League 2022 Competizione Erovnuli Liga Sport Calcio Edizione 34ª Organizzatore GFF Date dal 25 febbraio 2022al 3 dicembre 2022 Luogo  Georgia Partecipanti 10 Formula Girone all'italiana Risultati Vincitore Dinamo Tbilisi(19º titolo) Retrocessioni Sioni BolnisiLok’omot’ivi Tbilisi Statistiche Miglior marcatore Flamarion (19) Incontri disputati 180 Gol segnati 492 (2,73 per incontro) Cronologia della competizione 2021 2023 Manu...

Komando Resor Militer 133

Komando Resor Militer 133/Nani WartaboneLambang Korem 133/Nani WartaboneDibentuk13 September 2018Negara IndonesiaCabangTNI Angkatan DaratTipe unitKorem Tipe APeranSatuan Teritorial DaratBagian dariKodam XIII/MerdekaMakoremLimboto, GorontaloJulukanPasukan RimbaPelindungTentara Nasional IndonesiaMotoWira Dharma CaktiBaret H I J A U MaskotPohon Kelapa dan Senjata Tradisional GorontaloUlang tahun13 SeptemberTokohKomandanBrigjen TNI Hari PahlawantoroKepala StafKolonel Inf. Jaelan Ko...

 

Tyler James Williams

Tyler James WilliamsWilliams saat pemutaran perdana Let It Shine.Lahir9 Oktober 1992 (umur 31)Westchester County, New York, Amerika Serikat[1]PekerjaanAktorraperTahun aktif1996-sekarang Tyler James Williams (lahir 9 Oktober 1992) adalah aktor dan rapper asal Amerika Serikat. Dia memulai karirnya sebagai aktor cilik, membuat beberapa penampilan di Saturday Night Live, Little Bill dan Sesame Street.[2] Williams kemudian menjadi terkenal karena memainkan peran Chris Ro...

 

Retro Television Network

Retro Television NetworkJenisSiaran televisi berjaringanMerekRetro TVNegaraAmerika SerikatJangkauanNasionalSloganThe Best in Classic Television!PemilikRetro Television, Inc.IndukLuken Communications, LLCTanggal luncurJuli 2005Nama sebelumnyaRTN (2005-2009)RTV (2009-2013)Situs resmiwww.MyRetroTV.com Retro Television Network (bermerek on-air sebagai Retrotv) adalah sebuah jaringan televisi Amerika Serikat yang menyiarkan acara televisi klasik serta program baru-baru ini diproduksi. Dimiliki ole...

Floodplain

Land adjacent to a river which is flooded during periods of high discharge For other uses, see Floodplain (disambiguation). Paraná River floodplain, at its confluence with the headstream of the Paranaíba (on the right) and the Verde River, near Panorama, Brazil A floodplain after a one-in-10-year flood on the Isle of Wight Gravel floodplain of a glacial river near the Snow Mountains in Alaska, 1902 The Laramie River meanders across its floodplain in Albany County, Wyoming, 1949 This aggrada...

 

コルク

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年4月） コルクを打ち抜いて作った瓶の栓 コルク（木栓、�...

 

Six-party talks

Meetings on North Korea nuclear program For South Korea variety show, see Six-Party Talks (TV series). This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (August 2019) (Learn how and when to remove this message) Six-party talksChinese nameTraditional Chinese六方會談Simplified Chinese六方会谈TranscriptionsStandard MandarinHanyu PinyinLiùfāng Huìtá...

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

 

List of South African Airways destinations

South African Airways' first Airbus A350-900 arriving at John F. Kennedy International Airport in New York. As of December 2022[update] the airline does not serve this destination.[1] This is a list of South African Airways destinations, as of January 2024[update].[2] As of June 2016[update], South African Airways served eight destinations outside Africa. By that time, the top five international routes led from Johannesburg to New York C...

 

Law enforcement in Palau

The Euatel, Kabekl M'tal and Bul provide littoral fishery protection.[1] A Palauan police car The defense of Palau is the responsibility of the United States, but local police matters are handled by the Palau Police, the national police force. Some of the sixteen states also had separate police departments during the 1980s and 1990s. The Palau Bureau of Public Division of Marine Law Enforcement (DMLE)[2] is responsible for marine surveillance, maritime law enforcement, search ...

List of islands of Scotland

Map of the Inner and Outer Hebrides This is a list of islands of Scotland, the mainland of which is part of the island of Great Britain. Also included are various other related tables and lists. The definition of an offshore island used in this list is land that is surrounded by seawater on a daily basis, but not necessarily at all stages of the tide, excluding human devices such as bridges and causeways.[Note 1] Scotland has around 900 offshore islands,[1] most of which are ...

 

Operation Aurora

Series of cyberattacks conducted by Chinese threat actors Not to be confused with Aurora Generator Test. Operation AuroraDateJune–December 2009LocationNot specified – occurred on a worldwide scale.Result Diplomatic incident between the United States and ChinaBelligerents  United States  ChinaCasualties and losses Google intellectual property stolen[1] Operation Aurora was a series of cyber attacks performed by advanced persistent threats such as the Elderwood Group based...

 

Amoraim

Jewish scholars of the period from about 200 to 500 CE Rabbinical eras Chazal Zugot Tannaim Amoraim Savoraim Geonim Rishonim Acharonim vte Amoraim (Jewish Babylonian Aramaic: אמוראים [ʔamoraˈʔim], singular Amora אמורא [ʔamoˈra]; those who say or those who speak over the people, or spokesmen)[1] refers to Jewish scholars of the period from about 200 to 500 CE, who said or told over the teachings of the Oral Torah. They were primarily located in Babyloni...

Nichkhun

NichKhunSinhNichkhun Buck Horvejkul24 tháng 6, 1988 (36 tuổi)Rancho Cucamonga, California, Hoa KỳQuốc tịchThái LanHoa KỳNghề nghiệpCa sĩrapperngười mẫuvũ côngdiễn viênCha mẹTeeragiat Horvejkul (cha)Yenjit Horvejkul (mẹ)Người thânNichan Horvejkul (anh trai) Nichthima Horvejkul (em gái) Nachjaree Horvejkul (em gái)Sự nghiệp âm nhạcNhạc cụKeyboardpianoghi-taNăm hoạt động2008–nayHãng đĩaJYPHợp tác với2PM Nichkhun Buck H...

 

Sungai Bila (Sulawesi Selatan)

Untuk sungai Bila lain, lihat Sungai Bila. Sungai BilaSalo Bila, Sungai Salo BatuLokasi mulut sungaiTampilkan peta SulawesiSungai Bila (Sulawesi Selatan) (Indonesia)Tampilkan peta IndonesiaLokasiNegaraIndonesiaProvinsiSulawesi SelatanRegionKabupaten Sidenreng Rappang, Kabupaten WajoCiri-ciri fisikHulu sungaiPegunungan Botto Tallu - lokasiDesa Tanatoro, Kecamatan Pitu Riase, Kabupaten Sidenreng Rappang - elevasi2.600 m (8.500 ft) Muara sungaiDanau Tempe -...