İndirgeme polinom zamanı mı?

2024 Yazar: Fiona Howard | [email protected]. Son düzenleme: 2024-01-10 06:44

Hesaplamalı karmaşıklık teorisinde, bir polinom-zaman az altması, bir problemi diğerini kullanarak çözme yöntemidir. Polinom zaman az altmaları, karmaşıklık teorisinde hem karmaşıklık sınıflarını hem de bu sınıflar için tam problemleri tanımlamak için sıklıkla kullanılır. …

Polinom zamanı nedir?

Bir algoritmanın çalışma süresi, algoritma için giriş boyutunda bir polinom ifadesi ile üst sınırlanmışsa, yani, T(n)=O() polinom zamanlı olduğu söylenir. n^k) bazı pozitif sabitler için k.

Bir şeyin polinom zamanı olduğunu nasıl anlarsınız?

3 Cevaplar. Bazı k, C>0 için, n boyutundaki girdilerdeki çalışma süresi en fazla Cnk ise, bir algoritma polinomdur (polinom çalışma süresine sahiptir). Eşdeğer olarak, bazı k>0 için, n boyutundaki girişlerdeki çalışma süresi O(nk) ise, bir algoritma polinomdur.

Üssel zamanda azalmaya izin verilirse ne olur?

İndirgeme üstel zamana izin verilirse, orijinal problemi tamamen çözebilir ve hedef problemin önemsiz bir örneğini üretebilir Bu, NP'deki her problemin her birine indirgenebilir olduğu anlamına gelir. bu tür indirgemelerle ilgili diğer bir problem, bu nedenle NP'deki her problem üstel zaman az altmaları için NP-tamamlıdır.

Üslü algoritma nedir?

Bir algoritmanın üstel zaman olduğu söylenir, if T(n) 2^{poly(ile üst sınırlanır) )} , burada poli(n), n cinsinden bir polinomdur. Daha resmi olarak, eğer T(n) bazı sabitler için O(2^{nk) ile sınırlıysa, bir algoritma üstel zamandır. Ref:Wiki.}