News for hackers. Stuff that matters.
Re:Jun Fukuyama's P≠NP Page by jjjjjosh on Tuesday December 11, 2012 @12:57AM (#4903245)
Just to add: NP actually stands for "non-deterministic polynomial," meaning that if we had non-deterministic computers (like the NFAs you may remember from Automata Theory that can explore several different possibilities simultaneously) those types of computers could solve problems in NP in polynomial time.
Re:Jun Fukuyama's P≠NP Page by yuvadam on Tuesday December 11, 2012 @03:45AM (#4903696)
Non-deterministic Turing Machines, specifically. NFAs are obviously much weaker.