Surprising circuits
Date: 23 Mar 2005 23:53:51 -0800
Hi,
It was mentioned in my complexity theory course that it was possible to
do the following with circuits:
- compute ANY bool fct in cnst depth using *big-Oh(2^(n/2))* gates with
unbdd fan-in (trivial to do big-Oh(2^n), but to reduce it to
big-Oh(2^(n/2)).... (!)
- sort n integers, each of length n, in NC1 and... in AC0 also (!!)
- consider the following {0,1}^n -> {0,1}^n fct: f(x_1, ..., x_n) :=
(y_1, ..., y_n), where y_i = 1 iff there are at least 1 true variable
in x_1, ... x_i. It is claimed it can be done in AC0 *with a linear
number of wires* (!!!)
I find all of the above stmts hard to believe. If you have never seen
these problems, try to design a circuit that have any one of these
properties... you will think after an hour that these are impossible
constructions and you will understand my frustration ;)
Yet, I have been told by a reliable source that each of the above stmt
is true.
Is there someone who would have a hint on how to design such surprising
objects?
Thank you and have fun
K. V.
Relevant Pages
- Re: Charles Murray "The Plan" ends poverty
... The early days of electronic design automation are indeed interesting and if someone is going to write a history they had better hurry up. ... Donald Durr of RCA developed the first automated placement and wire routing program for LSI circuits in '65, ... I've had some experience with large systems in which the wrong circuit bounce in a switch or relay could set some relays to chatter and the system to wildly respond. ... Capacitors slowed down the switching, and helped the bouncing, but nowadays there are processors polling relays without debouncing circuits to determine whether they have switched. ...
(soc.retirement) - Re: Charles Murray "The Plan" ends poverty
... The early days of electronic design automation are indeed interesting and if someone is going to write a history they had better hurry up. ... Donald Durr of RCA developed the first automated placement and wire routing program for LSI circuits in '65, ... I've had some experience with large systems in which the wrong circuit bounce in a switch or relay could set some relays to chatter and the system to wildly respond. ... Capacitors slowed down the switching, and helped the bouncing, but nowadays there are processors polling relays without debouncing circuits to determine whether they have switched. ...
(soc.retirement) - Re: Charles Murray "The Plan" ends poverty
... The early days of electronic design automation are indeed interesting and if someone is going to write a history they had better hurry up. ... Donald Durr of RCA developed the first automated placement and wire routing program for LSI circuits in '65, ... I've had some experience with large systems in which the wrong circuit bounce in a switch or relay could set some relays to chatter and the system to wildly respond. ... Capacitors slowed down the switching, and helped the bouncing, but nowadays there are processors polling relays without debouncing circuits to determine whether they have switched. ...
(soc.retirement) - Re: Trying to understand how to design circuits
... >>> I am trying to understand the process by which the design of circuits ... One doesn`t know how someone decided to put a resistor ... >John, you seen to think that there is merit in coming up with something ...
(sci.electronics.design) - Re: AMD to produce ATI GPUs in Dresden
... Less than a year, assuming a good design. ... AMD has the necessary circuits, but ATI engineers have no experience ... AMD has a mature SOI process. ... migrating a GPU to SOI is a walk in the park. ...
(comp.sys.ibm.pc.hardware.chips) |
|
