Guruh Nigmatillayev Lazizxo’ja

Muhammad Al-Xorazmiy nomidagi (TATU) Toshkent Axborot Texnologiyalari Universiteti

216_21-guruh

Nigmatillayev Lazizxo’ja

Mavzu: P va NP sinflar,NP-toʻliq masalalar tushunchasi

Reja:

1. P va NP sinflar muammosi.

2. NP to’liq masala tushunchasi

Aytish mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay Matematika Instituti tomonidan tanlangan 7 ming yillik mukofot muammosidan biri, birinchi to'g'ri echim uchun 1 million dollar mukofotni olib yurish va hozir ham ochiq. P = NP muammosini isbotlash yoki echish informatika, matematika, kriptografiya, AI, multimedia ishlov berish, iqtisodiyot va boshqa sohalarda chuqur ta'sir ko'rsatishi mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin

• 
  Aytish mumkinki, bu kompyuter fanidagi eng mashhur echimsiz muammo. Clay Matematika Instituti tomonidan tanlangan 7 ming yillik mukofot muammosidan biri, birinchi to'g'ri echim uchun 1 million dollar mukofotni olib yurish va hozir ham ochiq. P = NP muammosini isbotlash yoki echish informatika, matematika, kriptografiya, AI, multimedia ishlov berish, iqtisodiyot va boshqa sohalarda chuqur ta'sir ko'rsatishi mumkin. Ushbu muammo noaniq tarzda aytilishi mumkin
  
• 
  "Kompyuter tomonidan tezda tekshirilishi mumkin bo'lgan har qanday muammoni kompyuter ham tezda hal qiladimi?".
  
• 
  Garchi bu masalaning mavjudligi 1950-yillarda Jon Nesh va Kurt Godel tomonidan muhokama qilingan bo'lsa-da, ushbu muammoni 1971 yilda Stefan Kuk o'zining mashhur "Teoremalarni tayyorlash protseduralarining murakkabligi" nomli maqolasida rasmiy ravishda kiritgan. Rasmiy bayonotga va muammoni tushuntirishga sho'ng'ishdan oldin, avval mavzu bilan bog'liq ba'zi ta'riflarni ko'rib chiqamiz.