ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

34 NP Compelteness

 
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3045
Location: Tehran

PostPosted: Wed Aug 12, 2020 6:26 pm    Post subject: 34 NP Compelteness Reply with quote

Turing Halting problem

مساله ای وجود دارد که می گوید یک کامپیوتری هست که یک بلوپرینت از ماشینی خاص را می گیرد برگه ورودی را هم می گیرد. سپس تشخیص می دهد که این ماشین برای این ورودی ساخته شده است یا خیر و در خروجی می دهد.
اما ثابت می شود که چنین ماشینی وجود ندارد.
قبل از این ماشین به عنوان ورودی یک کپی کننده می گذاریم. ورودی ماشین H می شود دو بلوپرینت پس خروجی می شود not stuck اما این ورودی را به یک ماشین منفی کننده می دهیم. بنابراین خروجی گیر می کند.
این سه ماشین را درقالب یک ماشین ببینید.
حالا فرض کنید به H یاد دادیم که هالت بشو. بنابراین خروجی H می شود stuck اما می بینیم این ماشین ما هالت نشد. Idea

این مساله غیرقابل حل توسط کامپیوتر است هیچ ربطی هم به زمان ندارد. Crying or Very sad

مساله رام نشدنی untractable کلا مغز ما مسایلی را حل می کند که رام شدنی هستند یعنی در زمان O(n^k) اما یک سری مسایلی هستند که فراتر از چندجمله ای ها هستند و رام نشدنی هستند.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum