3 ms·
>> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard That is actually incorrect, and is a common and
by vph 13y ago
>> NP-complete is essentially shorthand for belonging to a class of problems that are computationally very hard
That is actually incorrect, and is a common and serious misunderstanding of beginners. NP-complete problems are not hard to solve (e.g. via brute force). They are however very hard to solve efficiently (i.e. in polynomial time).
- reverius42 13y agoI think "computationally very hard" means exactly what you say NP-complete problems are ("very hard to solve efficiently"). Typically when one talks about the computational difficulty of an algorithm, they are talking about the computational resources it takes, not the amount a human has to think to come up with the algorithm.