Weak NP-completeness
id:
weak-np-completeness-244-13301810
title:
Weak NP-completeness
text:
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. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial. For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm requiring a
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Weak_NP-completeness
date created:
date modified:
2022-05-28T23:56:18Z
main entity:
{"identifier":"Q7977975","url":"https://www.wikidata.org/entity/Q7977975"}
image:
fields total:
13
integrity:
13