Terminology gap [entries|reading|network|archive]

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

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 :-)

[xpost |http://simont.livejournal.com/243239.html]

[personal profile] gerald_duckTue 2016-03-22 13:48

I've both heard and used the phrase "Halting-complete" before. I think I prefer it to "HP-complete" which sounds like the "P" ought to mean either "polynomial" or "Packard".

Link Reply to this
[personal profile] ptc24Tue 2016-03-22 17:38

HP complete - for solution, needs a wand-bearing wizard with a distinctive scar, and a bottle of brown sauce.

Link Reply to this | Thread
[personal profile] ptc24Wed 2016-03-23 08:28

Nope, hang on, better idea. Solving them involves summoning Cthulu.

Link Reply to this | Parent
[personal profile] fluffymormegilWed 2016-03-23 22:49

In speech I say "halting-complete", and I type fast enough that I can't be bothered truncating it in text.

Link Reply to this
[identity profile] writinghawk.livejournal.comFri 2016-03-25 07:36

One could imagine subdomains in which the Halting Problem is soluble, so 'uncomputable' is not an exact synonym.

Link Reply to this
[ go | Previous Entry | Next Entry ]
[ add | to Memories ]