
pee-space-poorna

computational jatilata siddhant mein, ack nirnay samasya pspace-poorna haye yadi ise input lambai (bahupad sthaan) mein bahupad smriti kii matra kaa upayog karke hull kiya jaa sakata haye aur yadi harr anya samasya jise bahupad sthaan mein hull kiya jaa sakata haye tou usey bahupad samay mein isamen parivartit kiya jaa sakata haye. peacepace-poorna samasyaon koo peacepace mein sabse kathin samasyaon key roop mein socha jaa sakata haye, bahupad sthaan mein hull karane yogya nirnay samasyaon kaa varg, kyonki aisee kissy bhee ack samasya key samadhan kaa upayog aasaani seey peacepace mein kissy bhee anya samasya koo hull karane key liye kiya jaa sakata haye.
peacepace-poorna honey key liye jaani jaane vaali samasyaon mein niyamit abhivyaktiyon aur sandarbh-samvedansheel vyakaranon key gunon kaa nirdhaaran karna, matratmak booliyan sootron kii sachchai kaa nirdhaaran karna, sanyojan anukoolan samasyaon key samadhanon key beach charan-darr-charan parivartan, aur kaee paheliyaan aur khel shamil hain.
siddhant.
ack samasya koo peacepace-poorna key roop mein paribhaashit kiya jaataa haye yadi ise smriti kii bahupad raashi (yeh peacepace seey sambandhit haye) kaa upayog karke hull kiya jaa sakata haye aur peacepace mein pratyek samasya koo dee gaee samasya key samatulya udaaharan mein bahupad samay mein badala jaa sakata haye.
peacepace-poorna samasyaon key baare mein vyaapak roop seey adhik prasiddh jatilata vargon pee (bahupad samay) aur np (gair-nirdhaarak bahupad samay) key baahar honey kaa sandeh haye, lekin yeh gyaat naheen haye. yeh gyaat haye kii way varg aine. see. key baahar sthit hain, joe atyadhik kushal samanantar algorithm key saath samasyaon kaa ack varg haye, kyonki aine. see. mein samasyaon koo input aakar key logridam mein space bahupad kii matra mein hull kiya jaa sakata haye, aur itani cumm matra mein samadhan karane yogya samasyaon kaa varg space padanukram dwara space mein sakhti seey nihit haye.
peacepace-poornata koo paribhaashit karane mein aamtaur parr jinn parivartanon parr vichaar kiya jaataa haye, way bahupad-samay kaee-ack katauti hain, parivartan joe ack prakaar kii samasya key ekal udaaharan koo ack alag prakaar kii samasya key samkaksh ekal udaaharan mein lete hain. haalaanki, turing reduction kaa upayog karke poornata koo paribhaashit karna bhee sambhav haye, jisamen ack samasya koo doosari samasya key liye ack subrutin koo coll kii bahupad sankhya mein hull kiya jaa sakata haye. yeh gyaat naheen haye kii kyaa inn dou prakaar kii katauti seey vibhinn vargon kii peacepace-poorna samasyaaen paida hoti hain. anya prakaar kii katauti, jaise kii kaee-ack katauti joe hamesha parivartit input kii lambai koo badhaati haye, parr bhee vichaar kiya gayaa haye.
space-poorna seton key liye burman-hartmanis anuman kaa ack sanskaran bataata haye kii aise sabhi sett ack jaise dikhate hain, iss arth mein kii way sabhi bahupad-samay bijection dwara ack dusare mein parivartit kiye jaa sakate hain.
udaaharan.
aupchaarik bhaashaaen.
ack niyamit abhivyakti sootra _ 1 diyaa gayaa haye, yeh nirdhaarit karate hue kii kyaa yeh apani varnamala parr pratyek string utpann kartaa haye, peacepace-poorna haye.
pahali gyaat peacepace-poorna samasya nirdhaarak sandarbh-samvedansheel vyaakaran key liye shabd samasya thee. sandarbh-samvedansheel vyaakaran key liye shabd samasya mein, kissy koo vyaakaranik parivartanon kaa ack samooh diyaa jaataa haye joe ack vaakya kii lambai koo badhaa sakata haye, lekin cumm naheen curr sakata haye, aur yeh nirdhaarit karna chaahata haye kii kyaa inn parivartanon dwara diyaa gayaa vaakya utpann kiya jaa sakata haye. nirdharvad" kii takniki sthiti (motey taur parr yeh darshaati haye kii pratyek parivartan seey yeh spasht hoe jaataa haye kii iska upayog kiya gayaa thaa) yeh sunishchit kartaa haye kii iss prakriya koo bahupad sthaan mein hull kiya jaa sakata haye, aur yeh darshaata haye kii raikhik sthaan mein computable pratyek (sambhavatah gair-nirdhaarak) prograam koo sandarbh-samvedansheel vyaakaran key parcing mein parivartit kiya jaa sakata haye, iss tarah seey joe nirdharvad koo sanrakshit kartaa haye. 1970 mein, sevich kii pramey ney dikhaaya kii pspace gair-nirdharanvad key tahat bund haye, jiska arth haye kii gair-nirdhaarak sandarbh-samvedansheel vyaakaran bhee pspace mein hain.
tark.
ack maanak peacepace-poorna samasya, jiska upayog kaee anya peacepace-poornata parinamon mein kiya jaataa haye, matrabaddh booliyan sootra samasya haye, joe booliyan santoshjanakta samasya kaa ack saamaanyikaran haye. matratmak booliyan sootra samasya ack booliyan abhivyakti key roop mein input letee haye, isake sabhi charr yaa tou saarvbhaumik roop seey yaa astitva mein matratmak hotey hain, udaaharan key liyeh
sootra _ 2
samasya kaa utpaadan matratmak abhivyakti kaa moolya haye. iss maan koo khojana pspace-poorna haye.
punarnirdharan.
punarsanrachana samasyaaen ack sanyukt samasya key samadhan key liye ack raajya sthaan kii connectivity seey sambandhit hain. udaaharan key liye, yeh pareekshan karna kii kyaa ack graph key dou 4-rangon koo ack dusare seey ack samay mein ack sheersh kaa rung badalane vaali chaalon dwara jodaa jaa sakata haye, pratyek charan mein ack vaidh 4-rung banaae rakhna, peacepace-poorna haye, bhale hii 3-rangon key liye ack hii samasya koo bahupad samay mein hull kiya jaa sakata haye. punarsanrachana samasyaon kaa ack anya parivaar, jiska upayog iss kshetra mein kaee anya samasyaon key sthaan-poornata pramaan key aadhar key roop mein matrabaddh booliyan sootron key samaan kiya jaataa haye, isamen gair-nirdhaarak baadha tark shamil hotaa haye, jisamen sthitiyaan ack baadha graph key abhivinyas hain, joe pratyek sheersh parr kitane kinaaron koo ander kii or unmukh kiya jaanaa chaahiye, aur jisamen ack ekal kinare key abhivinyas koo raajya seey raajya kii or modane key liye kuchh baadhaon key adheen hain.
paheli aur khel.
matratmak booliyan sootra samasya kii vyakhya dou khilaadiyon, ack satyapankarta aur ack galat saabit karane vaale dwara ack khel key roop mein kii jaa sakati haye. khilaadi aise kadam uthaate hain joe matratmak charr key liye moolyon koo bharate hain, jiss crum mein way nihit hotey hain, satyapankarta astitva mein matratmak charr koo bharata haye aur galat karane vaalaa saarvbhaumik roop seey matratmak charr koo bharata haye; yadi bharaa huaa sootra sahee hoe jaataa haye tou khel satyapankarta dwara jeetaa jaataa haye, aur anyatha galat karane vaale dwara. ack matratmak sootra tabhi sahee haye jaba satyapankarta key paas ack jeetane kii ranneeti hoe. isi tarah, kaee anya sanyojan khelon key vijeta yaa haarne vaale kaa nirdhaaran karane kii samasya peacepace-poorna hoe jaati haye. aise khelon key udaaharan joe space-poorna hain (jaba saamaanyikrit kiye jaate hain taaki unhein ack sootra _ 3 board parr khela jaa sakey) way hanks aur riversey khel hain. kuchh anya saamaanyikrit khel, jaise shatranj, checkers (draft), aur goo samay-poorna hotey hain kyonki dou paripurna khilaadiyon key beach ack khel bahut lamba hoe sakata haye, isaliye unake peacepace mein honey kii sambhavana naheen haye. lekin yadi chaalon kii sankhya parr ack bahupad baadhya kiya jaataa haye tou way peacepace-poorna hoe jaayenge.
ekal khilaadi dwara kheli jaane vaali paheliyon key liye bhee peacepace-poorna honah sambhav haye. inhen aksar punargathan samasyaon key roop mein vyakhya kii jaa sakati haye, aur isamen solitair game rush aavar, mahjong, atomics aur sokoban aur mechanical computer turing tumble shamil hain.
pspace-poornata input aakar sootra _ 4 key ack kaary key roop mein jatilata parr adharit haye, seema mein sootra _ 4 binaa seema key badhata haye. ack paaramparik sootra _ 6 board parr shatranj jaise seemit sankhya mein padon key saath paheli yaa khel peacepace-poorna naheen hoe sakate hain, kyonki unhein ack bahut badee lookup table kaa upayog karke nirantar samay aur sthaan mein hull kiya jaa sakata haye. inn khelon key peacepace-poorna sanskaranon koo taiyar karane key liye, unhein iss tarah seey sanshodhit kiya jaanaa chaahiye kii unaki sthiti kii sankhya aseemit hoe, jaise kii unhein ack sootra _ 3 board parr khelkar. kuchh mamalon mein, jaise kii shatranj key liye, yeye vistaar kritrim hain.

