Resource Bounded Unprovability of Computational Lower Bounds

Details Resource Bounded Unprovability of Computational Lower Bounds Resource Bounded Unprovability of Computational Lower Bounds

2005-03-31

arxiv.org/abs/cs/0503091v1

Computer Science

Computational Complexity

78 pages

Scientific paper

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-omega-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). This paper shows that P not= NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This result gives a unified view to the existing two major negative results on proving P not= NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-omega-consistency. We also show that the PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory S, where S is a consistent PT-extension of T.

Affiliated with

Also associated with

No associations

Rating

Resource Bounded Unprovability of Computational Lower Bounds 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 Resource Bounded Unprovability of Computational Lower Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource Bounded Unprovability of Computational Lower Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-720946