Maps of the interval, polynomial time, and polynomial space

Publisher Website
Google Scholar
Abstract
We use sequences of expansive maps of the interval to construct non-autonomous systems which appear to display "hyper-exponential loss of information" (defined below). A rigorous proof of this loss of information would prove that the class P of languages accepted in polynomial time is properly contained in the class PTAPE of languages accepted in polynomial space. Thus either P = NP or NP = PTAPE, where NP is the class of languages accepted by non-deterministic machines in polynomial time.

This publication has 0 references indexed in Scilit: