Koleksiyonlar

P - NP, NP-Complete ve Her Şey İçin Bir Algoritma

P - NP, NP-Complete ve Her Şey İçin Bir Algoritma


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Bu, dünyamızı güçlendirmek için basit ikili sayıları nasıl kullandığımızı araştıran, Algoritmalar ve Hesaplama üzerine yedi bölümlük bir dizinin altıncı makalesidir. İlk makale, Algoritmalar Yaşadığımız Dünyayı Nasıl Yönetir?, burada bulunabilir.

Bir problemi çözmek için oturduğumuzda, çok azımız çözmeye çalıştığımız problemin ne tür bir problem olduğunu anlamaya çalışırız. Neredeyse her durumda, bu sorunun cevabı ilginç bir alıştırmadır ve hatta bazı durumlarda sorunu çözmenize yardımcı olabilir, ancak başka pek bir şey değil. Ancak, Gezgin Satıcı Problemi gibi bir konuda durum çok farklı, bu yüzden teorik bilgisayar bilimcileri ve matematikçiler tarafından böyle bir çalışma ve araştırma konusu. Var herşey bir sorun olarak sınıflandırılmasıyla ilgili.

Sınıflandırma Problemleri: P Vs NP

Polinom zamanında çözüm üretebilen, bunun için verimli bir algoritma bildiğimiz problemler şöyle sınıflandırılır: P problemleriP anlamına geliyor polinom zamanı, bu durumda. Açıkçası bu, sınıflandırabildiğimiz ilk sorun alt kümesiydi: oradaki tüm bu sorunlardan, en azından bunları burada çözmeyi başardık. Listeleri sıralama, ağaçları dengeleme, verileri şifreleme gibi şeyler, etkili algoritmalarımız olan ve bu nedenle alt kümeye ait olan sorunlardır. P.

Daha sonra, başka bir sorun alt kümesi bulduk. P kendisi bir alt kümesiydi, NP sorunları. NP duruyor kesin olmayan polinom zamanama bizim amaçlarımız için, her bir modern bilgisayarın temelini oluşturan temel Turing dönemi bilgisayar biliminin bir parçası dışında bunun ne anlama geldiğini çok fazla bilmenize gerek yok. Bilmen gereken şey bu NP sorunları polinom zamanında sonuç üretebilecek bilinen bir algoritmaya sahip değilsiniz.

Ancak, size bir çözüm sunulursa NP sorunu, bunun doğru olduğunu doğrulamak kolaydır ve polinom zamanı veya daha az. Bu gerçeği, iPhone'larımızın kilidini her açtığımızda veya WhatsApp üzerinden mesaj gönderdiğimizde kullanırız. Anlaşılan, NP sorunları şifreleme için mükemmeldir; Şifrelemeyi hızlı bir şekilde çözen sorunu çözmenin tek bir yolu vardır, cevabı önceden almanız gerekir.

İLGİLİ: DÜNYAYI YÖNETEN 7 TEMEL ALGORİTMA

Doğal olarak, şifrelemeyi seviyoruz ve şimdilik güvenli olmasına sevindik, ancak şifrelemede pek çok sorun var. NP gerçekten, gerçekten verimli algoritmalara ihtiyacımız var. Bazı inanılmaz zeki insanların en iyi çabalarına rağmen, çok azı dışında hepsini çözme konusunda çok az ilerleme kaydedildi. NP sorunları bildiğimiz. Bu, son 50 yılın en büyük çözülmemiş matematik ve hesaplama problemlerinden birini oluşturdu: P - NP, olarak da adlandırılır P = NP.

Bu denklemin sorduğu şey, herhangi bir NP sorunu polinom zamanda çözülebilir, böylece NP sorunları Gerçekten mi P problemleri sadece düzgün bir şekilde çözülmesi gereken ya da NP sorunları Polinom zamanında hiçbir çözüm bulunamayan ve bu nedenle hangi algoritmaları geliştirirsek geliştirelim pratik olarak çözülemez kalan bir durumda?

Bu iki soruna bakarken, P - NPamaç, iki şeyden birini kanıtlamaktır: P = NPyani bir bütün olarak NP sorunları bir küme olarak - bildiklerimiz ve gelecekte keşfedebileceklerimiz dahil - aslında P ve polinom zamanında çözülebilir; veya P NP ve hangi algoritmayı bulursak bulalım, bir problemin zaman karmaşıklığında matematiksel bir taban olacaktır ve bu taban polinom zamandan daha büyük olacaktır.

Bu sorunun cevabı her iki şekilde de yeterince önemlidir ki, cevabı bulan kişi Clay Matematik Enstitüsü'nden bir milyon dolarlık ödül kazanacaktır, John Von Neumann, Alan Turing, Ada Lovelace ve diğer armatürlerin yanı sıra bilgisayar bilimleri panteonuna kurulumdan bahsetmeye bile gerek yok. .

Birçoğu için sorunu P - NP çoğunlukla matematik anlayışımızda doldurulması gereken bir boşluk olduğu gerçeğiyle ilgilidir. Her disiplinden matematikçiler ve bilim adamları bir bilgi boşluğundan nefret ederler, bu nedenle bu sorunun çözümü prensipte önemlidir. Yani, peşinde P = NP matematiksel olarak kanıtlanırsa, muazzam gerçek dünya çıkarımları vardır. P = NP. Nedenini anlamak için, hepsini birbirine bağlayan son iki problem grubunu bir araya getirmemiz gerekiyor.

NP-Hard ve NP-Complete

NP tamamlandı özel bir kategoridir NP sorunları polinom zamandan daha büyük zaman karmaşıklığına sahip olan, polinom zamanında doğrulanabilir ve şu şekilde bilinen bir dizi soruna ait olan NP-zor. NP-zor sorunlar esasen en az en zoru kadar zor olanlardır. NP sorunu, ancak polinom zamanda doğrulanabilir olması gerekmez.

Evrendeki her bir atom kümesinin tüm olası alt kümelerini saymak, bir NP-zor sorun. Polinom zamanında böyle bir sorunun çözülemeyeceğini kanıtlayamayız, ancak bu algoritmayı bulacağımıza veya onu çalıştıracak kadar güçlü bir makine yapacağımıza inanmak için bir neden yok ve birisi bize bir cevap verse bile, yapmayacağız. hatta bunu nasıl doğrulayacağını bile öğrenmeye başlar.

Bir diğeri NP-zor problem, herhangi bir tahta durumunda yapabileceğiniz en iyi hamle olan bir satranç hamlesini tanımlamaktır. Bunu belirlemek için, diğer her hareketin daha kötü bir sonuca yol açacağını bilmeniz gerekir ve bunu nasıl belirleyeceğimizi bilmenin tek yolu, her hareketin, karşı hamlenin vb. Her dallanma yolunu takip etmektir. verilen yönetim kurulu pozisyonu ile. Bu neredeyse sonsuz karar ağacının her dalının son sonucuna vardığınızda, en iyi sonucu alır ve bunun yapabileceğiniz en iyi hareket olduğunu söylersiniz.

Önümüzdeki birkaç milyar milyar yıl içinde bu ağaçta gezinmenin işlevsel olarak imkansız olduğunu bir kenara bırakırsak, bana belirli bir hareketin gerçekten yapabileceğiniz olası en iyi hareket olduğunu söylerseniz, bunu hızlı bir şekilde doğrulamamın bir yolu yoktur. Her hareketin her sonucunu keşfetmek için kullandığınız aynı kaba kuvvet permütasyon algoritmasına başvurmak zorunda kalacağım. Çözümün doğrulanması, sorunu çözmek için tam olarak gereken kadar uzun sürer.

Bu size biraz tanıdık geliyorsa, çünkü öyledir. Bu, aynı temel problemdir. Seyahat Eden Satıcı Sorunuyani temelde optimizasyonla ilgili. Görünüşe göre, bu, NP tamamlandı sorunlar; gerçekten sadece sayısız varyasyonu olan tek bir sorunu çözmeye çalışıyorsunuz ve bu varyasyonlar, temel iş, politika veya araştırma kararı verme olarak kabul ettiğimiz şeylerin tamamını kapsıyor.

Her Şey İçin Algoritma

Bu nedenle P = NP önemli. Kesin olarak bilemeyiz, ancak bu sorunun cevabının doğrudan doğruya işlediğine inanmak için her türlü neden var NP tamamlandı. İlk olarak, bir çözüm döndüren herhangi bir algoritma NP tamamlandı polinom zamandaki problem her birini çözmek için değiştirilebilir NP tamamlandı polinom zamandaki problem, çünkü hepsi özünde aynı problemdir.

Sadece bu değil, aynı zamanda tanımının bir parçası NP tamamlandı problem her problemdir NP herkese indirgenebilir NP tamamlandı sorun, yani çözen bir algoritma NP tamamlandı polinom zamanda da hepsini çözecek NP polinom zamandaki problemler; başka bir deyişle, çözme NP tamamlandı polinom zamandaki problem kanıtlıyor P = NP varsayılan olarak ve gerçek dünyadaki en zor hesaplama sorunlarının neredeyse tamamını kelimenin tam anlamıyla bir gecede çözer.

Yani bu, esasen bir NP tamamlandı polinom zamandaki problem her şey için bir algoritma. Bu nedenle P = NP, bu tuhaf, opak ses denklemi, eğer doğru olduğu kanıtlanabilirse ve bunu yapmanın tek gerçek yolu, NP tamamlandı polinom zamanda problem. Bu algoritma, bir anda tamamen farklı bir dünyanın kilidini açabilecek bir algoritma haline gelecekti. Kuantum hesaplama olasılığı etrafında çok fazla heyecan var çünkü bu, çözme konusunda en iyi şansımız olabilir. NP tamamlandı Polinom zamanında, yine de görülebilecek mi bırakılmayacak.

Algoritmalar ve Hesaplama ile ilgili dizimizin son makalesi, Kuantum Algoritmaları ve Klasik Sonrası Hesaplamanın Geleceği, burada bulunabilir


Videoyu izle: Açıklanan Turing Makineleri - Computerphile (Haziran 2022).


Yorumlar:

  1. Lamont

    Only posmeyte do it again!

  2. Farson

    Kesinlikle sizinle aynı fikirde. İçinde bir şeyler de benim için mükemmel bir düşünce. Tamamen seninle katılacağım.

  3. Garan

    Bu bana uymuyor.



Bir mesaj yaz