Talk:Gadget (computer science)

Latest comment: 12 years ago by Ruud Koot in topic PROD

Component design

edit

Shouldn't the article mention the term "component design" from Garey & Johnson? It seems to be used at least occasionally in the literature [1][2]. —Ruud 22:15, 27 February 2012 (UTC)Reply

PROD

edit

This article is an orphan, too technical, and WP is not a dictionary. Can you do something about these issues? Why should this not be merged into Computational complexity theory or some other article? Ideogram (talk) 22:28, 27 February 2012 (UTC)Reply

It's neither an orphan nor a dictionary definition. It could use a concrete example, such as their application in proving the NP-completeness of vertex cover or Hamiltonian cycle. With an example it would be too large to merge into computational complexity theory. —Ruud 22:38, 27 February 2012 (UTC)Reply
If it were to be merged anywhere, reduction would be a better place. Anyway, I've added an example, and have plans to do some more expansion based on some recent research on methods to search for optimized gadgets for inapproximability proofs. —David Eppstein (talk) 23:23, 27 February 2012 (UTC)Reply
That was quick, thanks. —Ruud 23:37, 27 February 2012 (UTC)Reply

Thanks

edit

Thanks, that helps. Ideogram (talk) 23:09, 27 February 2012 (UTC)Reply