[Solved]: NP Problem definition – verifiable on DFA vs. solvable on NFA

Problem Detail: 

So in complexity theory, I've run across different definitions for NP problems --

• Decision problems where a solution can be verified by a DFA in polynomial time
• Decision problems where a solution can be found by an NFA in polynomial time

Is there one of the above that is generally more accepted as the "go-to" definition in the academic community? If so, is there a reason? (If these "definitions" are incorrect – please feel free to correct me).

To me, the second definition makes more sense intuitively.

Asked By : C.B.

Answered By : Yuval Filmus

First, let me correct you: instead of a DFA there should be a deterministic Turing machine running in polynomial time, and instead of an NFA there should be a non-deterministic Turing machine running in polynomial time.

As you mention, both definitions are equivalent, and for this reason there is no single "go to" definition – you can use whatever definition is more appropriate in any single case.

Any formal development of complexity theory would necessitate picking one of these and then showing that the other is equivalent, but this is best left to the developers of these formal frameworks.

There are in fact many variants of Turing machines, so there are more than two definitions of NP. Even more equivalent definitions are provided by other models of computation such as RAM machines. Since all these definitions result in the same complexity class, they are all equally well definitions of NP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23643

3.2K people like this

 Download Related Notes/Documents