Circuits versus Trees in Algebraic Complexity
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)
: Circuits versus Trees in Algebraic Complexity
Abstract : . This survey is devoted to some aspects of the P = NP ?" problem over the real numbers and more general algebraic structures. We argue that given a structure M , it is important to nd out whether NPM problems can be solved by polynomial depth computation trees, and if so whether these trees can be eciently simulated by circuits. Point location, a problem of computational geometry, comes into play in the study of these questions for several structures of interest. 1 Introduction In algebraic complexity one measures the complexity of an algorithm by the number of basic operations performed during a computation. The basic operations are usually arithmetic operations and comparisons, but sometimes transcendental functions are also allowed [21-23, 26]. Even when the set of basic operations has been xed, the complexity of a problem depends on the particular model of computation considered. The two main categories of interest for this paper are circuits and trees. In section 2 and...
: Computer Science
Leave a comment
This contribution has not been reviewed yet. review?