Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
1 questions from the last 7 days
3
votes
1
answer
457
views
Has any problem been non-constructively proven to be in NP?
I believe that a standard way to prove that a language $L$ is in NP is to explicitly construct a witness $y$ for any instance $x$ in $L$ and an efficient algorithm that uses the witness to show that ...
- 1,216