News for hackers. Stuff that matters.

A comment on Classic Nintendo Games Are NP-Hard (2012). Parent comment

Re:Classic Nintendo Games Are NP-Hard (2012) by icen on Thursday December 28, 2017 @11:02AM (#16022762)
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.
[ Parent | on HN ]
Re:Classic Nintendo Games Are NP-Hard (2012) by betterunix2 on Thursday December 28, 2017 @11:58AM (#16023197)
Technically you could solve the problem testing a polynomial number of solutions after spending super-polynomial time choosing the solutions to test.
[ Parent | on HN ]