مسائل PSPACE كاملة

في نظرية التعقيد الحسابي، مجموعة مسائل التقرير بيسبايس-كاملة (بالإنجليزية: PSPACE-complete) هي مسائل تابعة لقسم التعقيد PSPACE، بحيث يمكن أن تختصر كل مسألة في PSPACE اليها بوقت متعدد الحدود (انظر التعقيد الكامل).

أي هذه المسائل هي المسائل الأصعب في القسم PSPACE من جهة أن حل هذه المسائل بسرعة -أي وقت الخوارزمية متعدد الحدود بالنسبة للمدخل - يفضي لحل كثير من المسائل المشابهة. حَدَسَ العلماء أن مثل هذه المسائل لاتتبع اقسام التعقيد P وNP، ولكن لا نعرف صحة هذا الحدس. ولكنها تقع خارج القسم إن سي، وذلك لأنَّ «إن سي» مجموعة جزئية للقسم ، وهذه القسم الاخير، أي PolyL , مجموعة جزئية فعلية (proper subset) ل-PSPACE .

نقاش

أول مسألة بيسبايس كاملة هي مسألة التقرير النحو الحساس للسياق القطعي.ومسألة التقرير للنحو الحساس للسياق ونريد أن نحدد ما إذا كان من الممكن للجملة المعطاة أن تُنتج عن طريق التحولات المُعرفة بواسطة هذا النحو.

وفي عام 1970، أظهرت نظرية سافيتش أن PSPACE=NPSPACE الأمر الذي يعني أن حتى القواعد النحوية الحساسة للسياق القطعية هي تابعة للقسم PSPACE.

ولكن المسالة النموذجية في PSPACE كاملة بشكل عام هي مسألة الصيغ المنطقية المكممة (التي عادة ما يتم اختصارها إلى "QBF" أو "TQBF" يشير حرف "T" إلى صحيحة أو حقيقة) وهذا على غرار المسألة SAT التي هي NP كاملة.

والدليل على أن مسألة الصيغ المنطقية المكممة "QBF" هي مسألة PSPACE كاملة هي إعادة ترتيب لمُبرهنة SAVITCH وهي لحد كبير أكثر تقنية.

أمثلة الألعاب التي هي PSPACE كاملة (عندما نعمم اللعبة لتكون على لوح بكبر nxn) هي لعبة هيكس ولعبة ريفيرسي ولعبة سوليتير. بعض الألعاب الأخرى المعممة، مثل لعبة الشطرنج ولعبة الرسم ذو المربعات (الدراما) وجو هي EXP كاملة لأن اللعبة بين اثنين من العابين المهرة من الممكن أن يستمر لفترة طويلة جدًا، لذلك فأنهم من غير المحتمل أن يتبعوا PSPACE . ولكن هذه المسائل PSPACE كاملة إذا حددنا عدد الحركات المسموح بها ليكون محدود بواسطة كثير حدود.

أمثلة على مسائل بيسبايس كاملة

التالي هو بعض مسائل بيسبايس كاملة مع المخطط التمهيدي للحساب الذي يعرض أنهم في «بيسبايس». ويمكن أن العثور على معظم الأمثلة في قائمة مسائل «بيسبايس كاملة».

مسألة الصيغ المنطقية المُكممة الصحيحة TQBF

مسألة الصيغ المنطقية المُكممة هي باعطائنا صيغة بوليانية مُكممة (quantified boolean formula) هل هي صحيحة؟ بشكل رسمي هي المجموعة التالية والتي نرمز لها ب- TQBF :

TQBF = : هي صيغة بوليانية مُكممة صحيحة

استراتيجيات الفوز في الألعاب

انظر إلى التعقيد الألعاب لمعظم الألعاب التي لها تكامل في «بيسبايس» أو صيغ التعقيد الأخرى التي تم تحديدها.

الجغرافيا المعممة

  • في المدخل <G,b>
  • إذا لم يكن لحرف بي حافة منتهية، أو رفضها.
  • وإلا إزالة حرف بي وجميع حوافه، ونسميه الرسم البياني الجديد جي 1.
  • مدخلات التشغيل بشكل متكرر <G1,bi>، حيث أن كل بي، تعتبر نقط نهاية الحواف من بي.
  • الرفض إذا تم قبول الجميع، أو القبول
  • استخدام المسافة: تعتبر عدد مستويات التكرار مساوية لعدد نقطة اللقاء جي. ويعتبر حجم المعلومات المخزنة في كل مستوي من التكرار مساوي لنقط اللقاء في جي. وبذلك يعتبر إجمالي المسافة خطي.2

تحديد ما إذا كان التعبير المنتظم يولد جميع السلاسل

معطى: تعبير نمطي (R ,(regular expression

المُخرج: هل R يولد جميع السلاسل؟ أي هل *L(R) = Σ

انظر أيضا

مراجع

  • Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. Section 8.3: PSPACE-completeness, pp. 283–94.
  • Michael R. Garey and دايفيد جونسون (عالم) (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Section 7.4: Polynomial Space Completeness, pp. 170–77.

وصلات خارجية

Read other articles:

2014 American resupply spaceflight to the ISS CRS-4 redirects here. For the Orbital ATK CRS-4 mission, see Cygnus CRS Orb-4. For the Sardinian research centre, see CRS4. SpaceX CRS-4CRS-4 Dragon approaching ISS on 23 September 2014NamesSpX-4Mission typeISS resupplyOperatorSpaceX / NASACOSPAR ID2014-056A SATCAT no.40210Websitehttps://www.spacex.com/Mission duration30 days (planned) [1]34 days, 13 hours, 46 minutes (achieved) Spacecraft propertiesSpacecraftDragon C106Spac...

 

JLL

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (novembre 2019). 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 ? ...

 

«Timor-Leste» redirige aquí. Para la isla completa, véase Timor. República Democrática de Timor-LesteRepública Democrática de Timor-Leste  (portugués)Repúblika Demokrátika Timor Lorosa'e  (tetun)Bandera Escudo Lema: Unidade, Acção, Progresso(en portugués: «Unidad, acción, progreso») Himno: Pátria(en portugués: «Patria») Capital(y ciudad más poblada) Dili8°33′13″S 125°34′42″E / -8.5536111111111, 125.57833333333 Idiomas oficial...

Artikel atau bagian mungkin perlu ditulis ulang agar sesuai dengan standar kualitas Wikipedia. Anda dapat membantu memperbaikinya. Halaman pembicaraan dari artikel ini mungkin berisi beberapa saran. Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. SMP Negeri 4 Tambun SelatanInformasiDidirikan1996; 28 tahun lalu (1996)[1]AkreditasiA[2]Nomor Statis...

 

Goadby Hall, 2013 Goadby Hall is a privately owned 17th-century country house located in Towns Lane, Goadby Marwood, Leicestershire. It is an historical Grade II* listed building.[1] The house was substantially renovated in 1750, when a new south front was built in the Palladian style. Five recessed central bays extend to two storeys with attics, the central three bays of which are pedimented with Doric order columns. Two flanking wings of two storeys have two bays each. The plainer n...

 

Election in Pennsylvania Main article: 2024 United States presidential election 2024 United States presidential election in Pennsylvania ← 2020 November 5, 2024 2028 →   Nominee Joe Biden(presumptive) Donald Trump(presumptive) Party Democratic Republican Home state Delaware Florida Running mate Kamala Harris(presumptive) TBA Incumbent President Joe Biden Democratic Elections in Pennsylvania Federal government U.S. President 1789 1792 1796 1800 1804 1808 18...

American record producer Allen RitterBackground informationBirth nameAllen Raphael Ritter[1]Born (1988-06-19) June 19, 1988 (age 35)Yonkers, New York, U.S.OriginDanbury, Connecticut, U.S.GenresHip hoptrapR&BOccupation(s)Record producersongwriterLabelsSony/ATVMusical artist Not to be confused with Allan Ritter. Allen Raphael Ritter (born June 19, 1988) is an American record producer and songwriter.[1] He has produced for a variety of artists, most notably Drake (Contro...

 

In Mexico City, Mexico Sporting event delegationCanada at the1968 Summer OlympicsIOC codeCANNOCCanadian Olympic CommitteeWebsitewww.olympic.ca (in English and French)in Mexico CityCompetitors139 (111 men and 28 women) in 14 sportsFlag bearerRoger JacksonMedalsRanked 23rd Gold 1 Silver 3 Bronze 1 Total 5 Summer Olympics appearances (overview)19001904190819121920192419281932193619481952195619601964196819721976198019841988199219962000200420082012201620202024Other related appearances190...

 

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

Ministry of Brazil Ministry of Foreign AffairsMinistério das Relações ExterioresItamaraty PalaceAgency overviewFormed13 November 1823[1]TypeMinistryHeadquartersItamaraty PalaceEsplanada dos Ministérios, Bloco HBrasília–DF15°48′36″S 47°52′12″W / 15.81000°S 47.87000°W / -15.81000; -47.87000Annual budgetBRL 2.3 billion (2022)[2]Agency executivesMauro Vieira, MinisterMaria Laura da Rocha[3], Secretary-General of Foreign AffairsChi...

 

Earldom in the Peerage of the United Kingdom For the 1833 steam locomotive Lord Wharncliffe, see Earl of Airlie (locomotive). 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. (January 2015) (Learn how and when to remove this message) Earldom of Wharncliffe Blazon Quarterly 1st & 4th, Argent, on a Bend between six Martlets Gules, three Bezants, a Canton Or, ...

 

British band Not to be confused with The Times showband. The TimesThe Times circa 1983. L-R: John East, Simon Smith and Ed BallBackground informationOriginLondon, EnglandGenresPost-punk, indie, power popYears active1980–presentLabelsWhaam! RecordsMembersEd BallPast membersJohn M EastDan TreacyAlan McGeeRay KentDick GreenPaul DamienPaul HeerenSimon SmithMisty WoodsWebsitemyspace.com/thetimeslondon The Times are a British indie band, the brainchild of Ed Ball, co-founder member of the Televis...

عملية أعمالمعلومات عامةصنف فرعي من عملية يستخدمه عمل تجاري تعديل - تعديل مصدري - تعديل ويكي بيانات   لمعانٍ أخرى، طالع عملية (توضيح). العملية في قطاع الأعمال، أي المعاملات التجارية، هي مجموعة من النشاطات أو المهام المرتبة والمترابطة التي تنتج خدمة معينة أو منتجا معين (�...

 

MOST Radio (PM2FGI)PT Radio Ramako Jaya RayaKotaJakartaWilayah siarJabodetabek dan SekitarnyaSlogan Most Music from the 80s & 90s (Slogan Bahasa Inggris) (10 Oktober 2017-sekarang) Memainkan musik terbaik era 80an & 90an (slogan Bahasa Indonesia) (10 Oktober 2017-sekarang) Most Greatest Hits (2021-sekarang) Delivering the most trending news (2022-sekarang) Frekuensi105,8 FMMulai mengudara 3 April 1983; 41 tahun lalu (1983-04-03) (sebagai Ramako) 10 Oktober 2017; 6 tahun lalu ...

 

Pour les articles homonymes, voir Révolution (homonymie). Cet article est une ébauche concernant l’astronomie. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Consultez la liste des tâches à accomplir en page de discussion. La révolution ou mouvement de révolution est, en mécanique céleste, un mouvement de translation périodique, circulaire ou elliptique[1]. La période de révolution, aussi appelée ...

Element ≥ (or ≤) each other element Hasse diagram of the set P {\displaystyle P} of divisors of 60, partially ordered by the relation x {\displaystyle x} divides y {\displaystyle y} . The red subset S = { 1 , 2 , 3 , 5 , 6 , 10 , 15 , 30 } {\displaystyle S=\{1,2,3,5,6,10,15,30\}} has one greatest element, viz. 30, and one least element, viz. 1. These elements are also maximal and minimal elements, respectively, of the red subset. In mathematics, especially in order theory, the greatest e...

 

Boar avatar of the Hindu god Vishnu VarahaMember of DashavataraVaraha killing Hiranyaksha and saving Bhumi, 1740 CE, Chamba paintingDevanagariवराहAffiliationAvatar of VishnuAbodeVaikunthaWeaponSudarshana Chakra, Kaumodaki, PanchajanyaSymbolsPadmaGenderMaleFestivalsVaraha Jayanti (August-September)GenealogyConsortLakshmi as Bhumi or Varahi (form of Bhumi)ChildrenNarakasura and Mangala Dashavatara SequencePredecessorKurmaSuccessorNarasimha Part of a series onVaishnavism Supreme deity Vi...

 

Laboratory apparatus Clamp HolderA clamp holderOther namesClamp Fastener, Boss Head, Right Angle Clamp HolderUsesElevate and move attached clampStabilize equipmentComponentsRing stand rod jaw and extension clamp jaw A clamp holder or clamp fastener is a piece of laboratory apparatus that is used to secure laboratory clamps, such as extension-type utility clamps, or other attachments to a retort stand or lab frame.[1] The material can be made up of brass, cast iron, stainless steel, al...

Eastern Catholic shrine in Johannesburg, South Africa The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: Shrine of Our Lady of the Cedars – news ...

 

Major archaeological horizon of the European Neolithic LBK redirects here. For other uses, see LBK (disambiguation). See also: Old Europe (archaeology) Linear Pottery cultureHorizonOld EuropeGeographical rangeCentral EuropePeriodNeolithicDatesc. 5500 BC — c. 4500 BCMajor sitesLangweiler, Bylany, Nitra, Zwenkau, Brunn am Gebirge, Elsloo, Sittard, Lindenthal, Aldenhoven, Flomborn, Rixheim, Rössen, Osłonki, Eythra, VrablePreceded byStarčevo–Kőrös–Criș culture, M...