A Weak Version of the Blum, Shub & Smale Model
Oh la la
Your session has expired but don’t worry, your message
has been saved.Please log in and we’ll bring you back
to this page. You’ll just need to click “Send”.
Your evaluation is of great value to our authors and readers. Many thanks for your time.
When you're done, click "publish"
Only blue fields are mandatory.
Your mailing list is currently empty.
It will build up as you send messages
and links to your peers.
besides you has access to this list.
Enter the e-mail addresses of your recipients in the box below. Note: Peer Evaluation will NOT store these email addresses log in
Your message has been sent.
Full text for this article was not available? Send a request to the author(s)
: A Weak Version of the Blum, Shub & Smale Model
Abstract : We propose a weak version of the Blum-Shub-Smale model of computation over the real numbers. In this weak model only a "moderate" usage of multiplications and divisions is allowed. The class of boolean languages recognizable in polynomial time is shown to be the complexity class P/poly. The main tool is a result on the existence of small rational points in semi-algebraic sets which is of independent interest. As an application, we generalize recent results of Siegelmann & Sontag on recurrent neural networks, and of Maass on feedforward nets. A preliminary version of this paper was presented at the 1993 IEEE Symposium on Foundations of Computer Science. Additional results include: Pi an efficient simulation of order-free real Turing machines by probabilistic Turing machines in the full Blum-Shub-Smale model; Pi an efficient simulation of arithmetic circuits over the integers by boolean circuits; Pi the strict inclusion of the real polynomial hierarchy in weak exponentia...
: Computer Science
Leave a comment
This contribution has not been reviewed yet. review?