loading page

Nondeterministic computation
  • Peifeng Wang
Peifeng Wang

Corresponding Author:[email protected]

Author Profile

Abstract

The execution of an algorithm on computing machines is studied. By Cantor’s diagonal argument, we show that, the number of executions within a computation on a nondeterministic Turing machine is asymptotically greater than the number of steps within a computation on a deterministic Turing machine. Thus a nondeterministic machine can have more computing power than a deterministic machine, therefore suggesting \(P\neq NP\).