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.