പി വേഴ്സസ് എൻ പി പ്രശ്നം

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
Jump to navigation Jump to search
Question dropshade.png കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ പരിഹരിയ്ക്കാനാകാത്ത പ്രശ്നം:
ഒരു പ്രശ്നത്തിന്റെ ഉത്തരം ശരിയാണോ എന്ന് എളുപ്പത്തിൽ ഒത്തുനോക്കാൻ പറ്റുമെങ്കിൽ പ്രശ്നം എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ സാധിയ്ക്കുമോ?
P സങ്കീർണതാ ക്ലാസും NP സങ്കീർണതാ ക്ലാസും തുല്യമല്ലെങ്കിൽ ഉള്ള അവസ്ഥ കാണിയ്ക്കുന്ന ചിത്രം. ഈ അവസ്ഥയിൽ P ക്ലാസ്സിനും NP ക്ലാസ്സിനും പുറത്ത് NP ക്ലാസ്സിൽ പെട്ട പ്രശ്നങ്ങൾ ഉണ്ടാകാം എന്ന ലാഡ്നേർസ് തിയറം തെളിയിയ്ക്കുന്നു.[1]

കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ ഇതുവരെ പരിഹരിയ്ക്കാത്ത ഒരു സുപ്രധാനസമസ്യയാണ് പി വേഴ്സസ് എൻ പി പ്രശ്നം. ഏറ്റവും ലഘുവായ ഭാഷയിൽ ഈ പ്രശ്നത്തെ ഇങ്ങനെ എഴുതാം : ഒരു പ്രശ്നത്തിന്റെ തന്നിട്ടുള്ള ഉത്തരം എളുപ്പത്തിൽ ശരിയാണോ എന്ന് പരിശോധിയ്ക്കാൻ സാധിയ്ക്കുമെങ്കിൽ ആ പ്രശ്നം എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ സാധിയ്ക്കുമോ? ഇവിടെ 'എളുപ്പത്തിൽ' എന്നതുകൊണ്ട് സാങ്കേതികമായി ബഹുപദ സമയസങ്കീർണതയോടെ ചെയ്യാൻ സാധിയ്ക്കുക എന്നാണ് അർത്ഥമാക്കുന്നത്.

1950 കളിൽ ആണ് ഈ പ്രശ്നം ചർച്ചകളിൽ വന്നു തുടങ്ങിയത്. ജോൺ ഫോർബ്സ് നാഷ് ജൂനിയർ നാഷണൽ സെക്യൂരിറ്റി ഏജൻസിയ്ക്ക് അയച്ച കത്തുകളിലും കുർട് ഗ്വോഡെൽ ജോൺ ഫോൺ ന്യൂമാൻ'ന് അയച്ച കത്തുകളിലും ഈ പ്രശനത്തിന്റെ പരാമർശം ഉണ്ട്. സ്റ്റെഫാൻ കുക്ക് 1971 ൽ പ്രസിദ്ധീകരിച്ച തന്റെ "The complexity of theorem proving procedures" എന്ന പ്രബന്ധത്തിലാണ് ഇതിന്റെ കൃത്യമായ രൂപം ആദ്യം പുറത്തുവന്നത്.[2] (ലിയോണിഡ് ലെവിൻ 1973 ലും സ്വതന്ത്രമായി ഇത് പുറത്തുവിട്ടിരുന്നു[3]) കമ്പ്യൂട്ടർ ശാസ്ത്രത്തിലെ ഏറ്റവും പ്രധാനപ്പെട്ട പരിഹരിയ്ക്കപ്പെടാത്ത സമസ്യയായി ഇതിനെ കണക്കാക്കുന്നു.[4] ക്ലേ മാത്തമാറ്റിക്സ് ഇൻസ്റ്റിറ്റ്യൂട്ട് തെരഞ്ഞെടുത്തിട്ടുള്ള സഹസ്രാബ്ദ പുരസ്‌കാര സമസ്യകളിൽ ഒന്നാണ് ഇത്. ആദ്യം ഈ പ്രശ്നം പരിഹരിയ്ക്കുന്നയാൾക്ക് ഒരു ദശലക്ഷം ഡോളറിന്റെ സമ്മാനത്തുകയും അവർ പ്രഖ്യാപിച്ചിട്ടുണ്ട്.

മുകളിൽ കൊടുത്തിട്ടുള്ള 'എളുപ്പത്തിൽ' എന്ന വാക്ക് കുറച്ചുകൂടി വിശദീകരിയ്ക്കണം. തന്നിട്ടുള്ള ഒരു പണി എളുപ്പത്തിൽ പൂർത്തിയാക്കുക എന്നാൽ ആ പണി ചെയ്യാൻ ബഹുപദ (polynomial) സമയസങ്കീർണതയുള്ള ഒരു വഴി (അൽഗോരിതം) ഉണ്ടെന്നാണ് ഇതിന്റെ അർത്ഥം. ഈ പ്രശ്നം ചർച്ച ചെയ്യുന്ന ചുറ്റുപാടിൽ ഉളവാകുന്ന മറ്റൊരു സങ്കീർണതാ ടൈപ്പ് എക്സ്പോണെൻഷ്യൽ സങ്കീർണതയാണ്. അത്തരം പ്രശ്നങ്ങളെ കഠിനമായ പ്രശ്നങ്ങൾ എന്നു വിളിയ്ക്കുന്നു. ബഹുപദസങ്കീർണതയോടെ പരിഹരിയ്ക്കാൻ സാധിയ്ക്കുന്ന പ്രശ്നങ്ങളുടെ ഗണത്തെ P ക്ലാസ് അഥവാ P ടൈപ്പ് പ്രശ്നങ്ങൾ എന്ന് വിളിയ്ക്കുന്നു. എന്നാൽ ഇത്തരത്തിൽ ബഹുപദ സങ്കീർണതയോടെ പരിഹരിയ്ക്കാൻ സാധിയ്ക്കാത്ത ചില പ്രശ്നങ്ങൾ ഉണ്ട്. ഇവയിൽ ചിലതിന്റെ ഉത്തരങ്ങൾ കിട്ടിയാൽ അവ ശരിയാണോ എന്ന് ബഹുപദ സങ്കീർണതയോടെ തന്നെ ഒത്തു നോക്കാൻ കഴിഞ്ഞേക്കും. ഇത്തരം പ്രശ്നങ്ങളുടെ ഗണത്തെ NP ക്ലാസ് പ്രശ്നങ്ങൾ എന്ന് വിളിയ്ക്കുന്നു. നോൺ-ഡിറ്റർമിനിസ്റ്റിക് പോളിനോമിയൽ ടൈം എന്നാണ് NP എന്നതിന്റെ മുഴുവൻ രൂപം.[Note 1]

സുഡോകു കളി ഉദാഹരണമായി എടുക്കുക. ഒരു സുഡോകു ബോർഡിൽ വിവിധ സംഖ്യകൾ നിറച്ച് ആരെങ്കിലും തന്നാൽ അത് ശരിയാണോ എന്ന് നമുക്ക് എളുപ്പത്തിൽ പരിശോധിയ്ക്കാം. ഓരോരോ വരിയും നിരയുമായി പരിശോധിച്ചാൽ മതി. എത്ര വരിയും നിരയുമുണ്ടോ അത്രയ്ക്കും ചെക്കുകൾ നടത്തിയാൽ മാത്രം മതി. അതായത് ഒരു സുഡോക്കുവിന്റെ ഉത്തരം ശരിയാണോ എന്ന് ചെക്ക് ചെയ്യാനുള്ള അൽഗോരിതത്തിന്റെ സമയ സങ്കീർണത അതിന്റെ വലുപ്പത്തിന് രേഖീയ അനുപാതത്തിൽ ആണ്. എന്നാൽ ഇത്തരം ഒരു ബോർഡ് തന്നാൽ അതിന്റെ ശരിയായ ഉത്തരം കണ്ടുപിടിയ്ക്കാനുള്ള ഏറ്റവും മികച്ച അൽഗോരിതം പോലും എക്സ്പോണെൻഷ്യൽ സമയം എടുക്കും. അതായത് സുഡോകു ഇപ്പോൾ NP ക്ലാസ്സിൽ പെട്ട ഒരു പ്രശ്നമാണ് (എളുപ്പത്തിൽ ചെക്ക് ചെയ്യാൻ പറ്റുന്നത്). ഇത് ഇപ്പോൾ P ക്ലാസ്സിൽ പെടുന്നില്ല. ഇത്തരത്തിൽ എളുപ്പത്തിൽ ഉത്തരം ചെക്ക് ചെയ്യാൻ പറ്റുന്ന, എന്നാൽ എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ പറ്റാത്ത ആയിരക്കണക്കിന് പ്രശ്നങ്ങൾ ഉണ്ട്. എന്നാൽ ഇതിൽ ഇത്തരം പ്രശ്നങ്ങളിൽ ഏതെങ്കിലും ഒന്നിനെ എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ കഴിഞ്ഞാൽ ഈ ഗണത്തിലെ മറ്റെല്ലാ പ്രശ്നങ്ങളെയും എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ സാധിയ്ക്കും എന്ന ഗവേഷകർ കണ്ടെത്തിയിട്ടുണ്ട്. ഈ പ്രത്യേകതയെ NP കമ്പ്ലീറ്റ്നെസ് എന്ന് വിളിയ്ക്കുന്നു. ദശാബ്ദങ്ങളായി ഇവയ്ക്ക് ബഹുപദ സങ്കീർണതയുള്ള അൽഗോരിതങ്ങൾ കണ്ടെത്താൻ ശ്രമം നടക്കുന്നുണ്ടെങ്കിലും ഇതു വരെ ഒന്നും കണ്ടെത്തിയിട്ടില്ല. അതിനാൽ ഇത്തരം അൽഗോരിതങ്ങൾ കണ്ടെത്താൻ സാധ്യമല്ല എന്ന് ശാസ്ത്രജ്ഞർ വിശ്വസിയ്ക്കുന്നു. എന്നാൽ സാധ്യമല്ല എന്ന് തെളിയിയ്ക്കപ്പെട്ടിട്ടില്ല.

P = NP? എന്ന പ്രശ്നത്തിന് അതേ എന്നാണ് ഉത്തരം എങ്കിൽ സുഡോകു പോലുള്ള പ്രശ്നങ്ങൾ പരിഹരിയ്ക്കാനുള്ള ബഹുപദ സങ്കീർണതയുള്ള അൽഗോരിതങ്ങൾ ലഭിയ്ക്കും. അല്ല എന്നാണെങ്കിൽ ഇത്തരം പ്രശ്നങ്ങൾ ഒരിയ്ക്കലും എളുപ്പത്തിൽ പരിഹരിയ്ക്കാൻ പറ്റില്ല എന്ന് മനസ്സിലാക്കാൻ സാധിയ്ക്കും.

ഈ പ്രശ്നത്തിന്റെ ശരിയായ ഒരു തെളിവ് ഗണിതം, ക്രിപ്ടോഗ്രഫി, അൽഗോരിതഗവേഷണം, നിർമിത ബുദ്ധി, ഗെയിം തിയറി, മൾട്ടിമീഡിയ പ്രോസസ്സിംഗ്, തത്ത്വശാസ്ത്രം, സാമ്പത്തികശാസ്ത്രം തുടങ്ങിയ പല മേഖലകളിലും ദൂരവ്യാപകമായ ഫലങ്ങൾ ഉളവാക്കും.[5]

കുറിപ്പുകൾ[തിരുത്തുക]

  1. A nondeterministic Turing machine can move to a state that is not determined by the previous state. Such a machine could solve a NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.

അവലംബങ്ങൾ[തിരുത്തുക]

  1. R. E. Ladner "On the structure of polynomial time reducibility," Journal of the ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
  2. Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. 
  3. L. A. Levin (1973). "Универсальные задачи перебора" (റഷ്യൻ ഭാഷയിൽ). 9 (Problems of Information Transmission ed.): 115–116. 
  4. Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. doi:10.1145/1562164.1562186. 
  5. Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491. 

കൂടുതൽ വായനയ്ക്ക്[തിരുത്തുക]

പുറംകണ്ണികൾ[തിരുത്തുക]

"https://ml.wikipedia.org/w/index.php?title=പി_വേഴ്സസ്_എൻ_പി_പ്രശ്നം&oldid=2831824" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്