Terminology gap (Reply) [entries|reading|network|archive]

[ userinfo | dreamwidth userinfo ]
[ archive | journal archive ]

[personal profile] simont Tue 2016-03-22 09:53
Terminology gap

Yesterday in a technical conversation I used the phrase ‘HP-complete’.

I had intended it, by analogy with ‘NP-complete’, to mean that if the problem under discussion could be solved, the solution would necessarily include a solution to the Halting Problem, i.e. the problem was as hard as the Halting Problem, i.e. uncomputable.

There are several other well known ‘-complete’ phrases which analogise in the same way – ‘Turing-complete’ and ‘AI-complete’ – and it seems to me that ‘HP-complete’ fits right into this framework and has a technically precise and useful meaning. But for some reason it isn't in common usage in the way that those other ‘-complete’ phrases are, so the person I was talking to didn't get what I meant and I had to explain. Bah. I don't see why it isn't part of the standard lexicon, for all the same reasons!

I suppose we already have the word ‘uncomputable’, so you could argue that we don't need ‘HP-complete’ as a synonym. But I think it's not quite a synonym, in that it also conveys a hint about why it's uncomputable, or at least about the train of thought that made me conclude that it was.

(I suppose it's conceivable, in my original context, that I should have chosen ‘HP-hard’ rather than ‘HP-complete’ – I don't think I'd intended to rule out the possibility that the problem under discussion was harder than the Halting Problem :-)

Link Read Comments
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
Account name:
If you don't have an account you can create one now.
HTML doesn't work in the subject.


Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.