1
Here's a simple argument that the ability to find a witness in polynomial time would imply P=NP:
Assume that we have a poly-time algorithm for finding a witness to any YES-instance of some NP-complete problem. Then there exist absolute constants $k$ and $c$ such that when run on a valid input of size $n$, the algorithm completes after at most $n^k + c$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
