p vs np problemi

hunyadi
deterministik olmayan Turing makinesi tarafından t polinom zamanda çözülebilen ve t polinom zamanda çözümü kanıtlanan problemlerin, t polinom zamanda deterministik Turing makinesi tarafından çözülebilen ve t zamanda çözümü kanıtlanan problemlere indirgenebileceğini iddia eden önermenin genel adı. hesaplama karmaşıklığı teorisinde en ünlü problemlerden biridir ve hala çözülememiştir.