1

I was wondering if NP problems were actually solvable in P time, then what will be the impact on Video Games, if any ?

Devey Singh
  • 27
  • 1
    In case you are talking about video games then for that, $NP$ problems are solved in polynomial time, approximations are enough. – Guy Apr 03 '14 at 13:52
  • The above is assuming that you are talking about the code behind running an AI system, or whatever. If not, then I am not really sure what you're asking about. – Guy Apr 03 '14 at 13:53
  • I was wondering if it would impact the process of creating a world or an environment ? – Devey Singh Apr 03 '14 at 14:03
  • Are you referring to rendering the images/calculation in the physics engine? In that case, we have very efficient approximation algorithms. – Guy Apr 03 '14 at 14:05
  • It has been shown that in general, sokoban and Minesweeper are NP-complete. – MJD Apr 03 '14 at 14:06
  • @MJD just because a computer can't beat it efficiently, doesn't mean I can't. – Guy Apr 03 '14 at 14:07

1 Answers1

1

Depends on whether or not they also developed an effective algorithm for solving some NP-complete problems. Just knowing that the two classes are related doesn't necessarily tell you how to solve it in P time.

And being able to solve something in polynomial time doesn't mean that you can solve it very quickly: If the running time of the algorithm is n^3 * one googleplex, it's still polynomial time but probably not practically solvable.

And anyway, the only problem that I know of that is NP-complete that is remotely related to video games is the Travelling salesman problem, so better pathfinding algorithms?

So in short, I doubt it would have much impact. Though it does very much depend on HOW it is proven. Since our current methods don't seem to work, a proof would most likely be a great leap forward in mathematics, provided it was a proof method that could be applied to other problems.

Gabriel_s_syme
  • 177
  • http://programmers.stackexchange.com/questions/148836/what-would-be-the-impact-of-p-np

    A similar question on another stack exchange which probably answers your question better.

     – Gabriel_s_syme Apr 03 '14 at 14:09