2 ms·
> can't we just check the proof by using their alleged algorithm on some np-hard problems? Not necessarily. An algorithm may be polynomial but impractical for
by coliveira 4y ago
> can't we just check the proof by using their alleged algorithm on some np-hard problems?
Not necessarily. An algorithm may be polynomial but impractical for all but the most trivial cases. Moreover the algorithm may be very difficult to implement correctly.
- nestorD 4y agoThe large constant problem might not apply here as NP problems suffer from an exploding complexity: you don't need to grow them that much to reach a point where that constant would be a non-issue. Ease of implementation could definitely be an issue.