Talk:Strong NP-completeness

More examples

A list of strongly NP-hard problems would be fine! The article does not even mention only one example. —Preceding unsigned comment added by 92.73.110.246 (talk) 06:22, 16 October 2009 (UTC)

Merge

I am excited to see if this article will contain anything that can't easily be put into other NP articles. I suggest merge... Medico80 22:45, 7 August 2006 (UTC)

Haha, umm...a good question. As the one who created it I wouldn't have any problem with merging the information into the NP-completeness article; I just saw some article linking to this (non-existent) page so thought creating it would be a good idea. If the info is put into the NP-completeness article, should we make this one redirect there? Flaxter 02:49, 8 August 2006 (UTC)

Yes, I think that is the way to do it. Cheers :-) Medico80 19:36, 9 August 2006 (UTC)

I agree. —Preceding unsigned comment added by 80.229.163.140 (talk) 20:06, 13 October 2007 (UTC)

strong-NP-hardness not defined correctly

the definition the article gives is:

A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it;

This is not correct, right would be:

A problem is said to be strongly NP-hard if any strongly NP problem has a polynomial reduction to it2A02:1205:34D9:C2F0:74E5:7FDB:9D8C:1944 (talk) 12:31, 9 April 2014 (UTC)

Also, about the same sentence

A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it

According to Garey and Johnson 1978, 1979, it seems that the correct sentence would be:

A problem is said to be strongly NP-hard if a strongly NP-complete problem has a pseudo-polynomial reduction to it Bweps (talk) 11:37, 4 June 2015 (UTC)