🚀 go-pugleaf

In article <1992Aug28.143621.1917@mcc.com>, praveen@sirius.mcc.com
(Praveen Vishakantaiah) writes:
>
>
  some stuff deleted....

An interesting posting; however it elicits a couple of comments....

> 
> Holger> I cannot imagine that everyone is interested in design
> Holger> (comp.lang.vhdl, comp.lang.verilog, comp.sys.mentor, comp.lsi*),
> Holger> but nobody in testing of all the stuff produced. 
> 
> Well, isn't testing harder than designing ;-). Nobody has proved VLSI 
> design to be an NP-complete problem (as far as I know)!
> 

  That is not true. There is a mulititude of problems that are NP-complete
in physical design of VLSI, including placement, routing, pin assignment, etc. 

> 
> Rise and shine, all you testing folks. Spend some time posting useful
> discussions pertaining to VLSI testing. Don't work too hard on the testing
> problem [I hope my advisor does not see this:-)]. After all, the testing
> problem was NP-complete, is NP-complete and will be NP-complete!! 
                                               ^^^^^^^^^^^^^^^^^^^^

   ... until the question P = NP ? remains unresolved.


> Praveen Vishakantaiah.

Raghu Hudli
-----------------------------------------------------------------------
Raghu V. Hudli                       Tel:   (914) 892-4188
IBM Corporation                      Fax:   (914) 892-4316 
E. Fishkill, NY                      email: raghu@vnet.ibm.com
------------------------------------------------------------------------
Disclaimer: The opinions/views expressed here are mine and my employer
does not necessarily concur with me.

In <1992Aug28.143621.1917@mcc.com> praveen@sirius.mcc.com (Praveen Vishakantaiah) writes:

>Holger> I cannot imagine that everyone is interested in design
>Holger> (comp.lang.vhdl, comp.lang.verilog, comp.sys.mentor, comp.lsi*),
>Holger> but nobody in testing of all the stuff produced. 

>Well, isn't testing harder than designing ;-). Nobody has proved VLSI 
>design to be an NP-complete problem (as far as I know)!

>Rise and shine, all you testing folks. Spend some time posting useful
>discussions pertaining to VLSI testing. Don't work too hard on the testing
>problem [I hope my advisor does not see this:-)]. After all, the testing
>problem was NP-complete, is NP-complete and will be NP-complete!! 

I don't think that you can rate the design process by the complexity of an 
algorithm, but even for testing, NP-completeness could have been shown for
combinational deterministic TPG (polynomial transformation to SAT problem) 
only. Sequential TPG has the additional time parameter (this might come close
to Turing's halting problem). Your opinion is quite correct. Everybody who
has put together two gates successfully, might be called a "designer"
(I am really afraid that some of the students which have heard - not learnt -
design courses here will go to industry and design some microprocessor which
will control parts of my car :-), just self-criticism, forget it), but
design verification or testing really requires some skills.

>Harlow> Come on, Janak: you have lots of good things going on at UIUC: how
>Harlow> about some timely, controversial postings from you and/or your
>Harlow> group?

>Although this is a very good and useful suggestion, it is very unlikely 
>that researchers are ready to discuss their ideas openly due to competitive 
>reasons. But, we can always discuss published work as well as get feedback
>from people in the industry as to the research direction in testing which
>would be useful to them.

This is what Nikolaus and I intended when we proposed this group. I would not
expect that for instance Janak talks about his recent improvement that he 
just put into his software, but if he contributes a paper to some conference, 
and is accepted and the date of the delivery of the final version is over 
(important!), he could talk about it, and may profit from a discussion on it.

>Harlow> Suppose we had a manufacturing line whose yield was 100%...  
>Harlow> would we then not need to test products? .........
>Harlow> .................
>Harlow> More generally speaking, how much of what we call testing is
>Harlow> actually a cover for lack of design verification?

See my reply to the original posting.

>Praveen Vishakantaiah.

>------------------------------------------------------------------------------
>-- Microelectronics and Computer Technology Corporation, | Ph : (512)338-3736|
>-- 3500 W. Balcones Center Drive                         | e-mail :          |
>-- Austin, TX 78759.                                     | praveen@mcc.com   |
>------------------------------------------------------------------------------
>-- ALSO A HARD WORKING MEMBER OF :-)
>-- Computer Engineering Research Center,                 | Ph : (512)471-8013|
>-- University of Texas, Austin.             e-mail : praveen@cerc.utexas.edu | 
>-----------------------------------------------------------------------------

-- 
|  |   / Holger Veit             | INTERNET: veit@du9ds3.uni-duisburg.de
|__|  /  University of Duisburg  | BITNET: veit%du9ds3.uni-duisburg.de@UNIDO
|  | /   Dept. of Electr. Eng.   | "No, my programs are not BUGGY, these are
|  |/    Inst. f. Dataprocessing |          just unexpected FEATURES"

> 
> Holger> I cannot imagine that everyone is interested in design
> Holger> (comp.lang.vhdl, comp.lang.verilog, comp.sys.mentor, comp.lsi*),
> Holger> but nobody in testing of all the stuff produced. 

> 
> Praveen> Well, isn't testing harder than designing ;-). Nobody has proved VLSI 
> Praveen> design to be an NP-complete problem (as far as I know)!
> 

> Hudli> That is not true. There is a mulititude of problems that are NP-complete
> Hudli> in physical design of VLSI, including placement, routing, pin assignment, etc. 

I should have specified it more clearly. I meant logic and functional
design. Yes, placement, routing etc. are NP-complete and are part of the
design process. But then I consider testing also to be an essential part of
VLSI design and the whole purpose of comparing design and test is lost. 

Thanks for pointing it out.

> Praveen> After all, the testing problem was NP-complete, is NP-complete 
> Praveen> and will be NP-complete!! 
               ^^^^^^^^^^^^^^^^^^^^

> Hudli>   ... until the question P = NP ? remains unresolved.

Or until the computer scientists/mathematicians give up:-) 

Praveen Vishakantaiah.

------------------------------------------------------------------------------
-- Microelectronics and Computer Technology Corporation, | Ph : (512)338-3736|
-- 3500 W. Balcones Center Drive                         | e-mail :          |
-- Austin, TX 78759.                                     | praveen@mcc.com   |
------------------------------------------------------------------------------
-- ALSO A HARD WORKING MEMBER OF :-)                     |
-- Computer Engineering Research Center,                 | Ph : (512)471-8013|
-- University of Texas, Austin.             e-mail : praveen@cerc.utexas.edu | 
-----------------------------------------------------------------------------

Logic minimization is also NP-hard.

In fact, damn near any interesting design or testing teachnique is NP-hard (after all, that
is what makes it interesting).

Kevin