3 ms·
In the worst case, it is commonly thought (this is P vs NP) that you will have to test a super-polynomial number of solutions. It doesn't have to be all of them
by icen 9y ago
In the worst case, it is commonly thought (this is P vs NP) that you will have to test a super-polynomial number of solutions. It doesn't have to be all of them.
- betterunix2 9y agoTechnically you could solve the problem testing a polynomial number of solutions after spending super-polynomial time choosing the solutions to test.