Solving the P/NP Problem under Intrinsic Uncertainty

Details Solving the P/NP Problem under Intrinsic Uncertainty Solving the P/NP Problem under Intrinsic Uncertainty

2008-11-04

arxiv.org/abs/0811.0463v2

Computer Science

Computational Complexity

typos corrected, figure added, statements clarified

Scientific paper

Heisenberg's uncertainty principle states that it is not possible to compute both the position and momentum of an electron with absolute certainty. However, this computational limitation, which is central to quantum mechanics, has no counterpart in theoretical computer science. Here, I will show that we can distinguish between the complexity classes P and NP when we consider intrinsic uncertainty in our computations, and take uncertainty about whether a bit belongs to the program code or machine input into account. Given intrinsic uncertainty, every output is uncertain, and computations become meaningful only in combination with a confidence level. In particular, it is impossible to compute solutions with absolute certainty as this requires infinite run-time. Considering intrinsic uncertainty, I will present a function that is in NP but not in P, and thus prove that P is a proper subset of NP. I will also show that all traditional hard decision problems have polynomial-time algorithms that provide solutions with confidence under uncertainty.

Affiliated with

Also associated with

No associations

Rating

Solving the P/NP Problem under Intrinsic Uncertainty does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving the P/NP Problem under Intrinsic Uncertainty, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving the P/NP Problem under Intrinsic Uncertainty will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183989