4
votes
Does the use of True randomness work in this proof for P does not equal NP
I think you don’t quite understand what non-deterministic means.
Take the travelling salesman problem. Say 50 cities, and we ask if you can visit all of them and return to the start within 1950 miles. ...
- 28.4k
3
votes
Does the use of True randomness work in this proof for P does not equal NP
It's a bit unclear how you make a leap from "The problem is truly random" to "the result can't be predicted".
Let's imagine another example: you use True Randomness to shuffle N ...
- 131
3
votes
Polynomial Hierarchy - the difference between $\Pi$ and $\Sigma$
Your conception of the variable ordering is misleading you, and we can indeed add a dummy variable at the beginning.
If we have a $\Pi_1\mathrm{P}$-problem $S$, we can write it as $S(x) \...
- 2,713
2
votes
Does the use of True randomness work in this proof for P does not equal NP
It seems like you misunderstand what NP stands for and what the 3SAT problem is. NP stands for Nondeterministic Polynomial, which means that a non-deterministic Turing machine can guess a solution to ...
Only top scored, non community-wiki answers of a minimum length are eligible