Login Preferences
About News Publications Statistics Downloads API Guide License How to use Preferences
bn:03684110n
Noun Named Entity
Categories: Weakly NP-complete problems, Computational complexity theory, Complexity classes
EN
Weak NP-completeness  weakly NP-complete  weakly NP-hard
EN
In computational complexity, an NP-complete problem is weakly NP-complete if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved, rather than the base-two logarithms of their magnitudes. Wikipedia
Definitions
Relations
Sources
EN
In computational complexity, an NP-complete problem is weakly NP-complete if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved, rather than the base-two logarithms of their magnitudes. Wikipedia
Set of computational problems for which there is an algorithm solving them in polynomial time in the dimension of the problem and the magnitudes of the data involved, rather than the base-two logarithms of their magnitudes Wikidata
IS A
complexity class
PART OF
NP-complete
pseudo-polynomial time
Wikipedia
EN
Weak NP-completeness
Wikidata
EN
weak NP-completeness
Wikipedia Redirections
EN
weakly NP-complete, weakly NP-hard

Please note that, in order to improve your browsing experience on this website, BabelNet® uses various types of cookies, including: browsing functionality, performance and statistical cookies.

By continuing to browse the site you are agreeing to our use of cookies. OK

License