2 ms·
Except that O(|V|^2 log|V|) is still polynomial. (|V| > log|V|), therefore (|V|^2 |V| == |V|^3) > (|V|^2 log |V|). As a polynomial is a (loose) upper-bound, i
by Groxx 17y ago
Except that O(|V|^2 log|V|) is still polynomial.
(|V| > log|V|), therefore (|V|^2 |V| == |V|^3) > (|V|^2 log |V|). As a polynomial is a (loose) upper-bound, it cannot be greater than polynomial time, thus !NP-Complete.
- deleted 17y ago[deleted]