[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lojban] How do I say "NP-complete"?
NP-complete problems are an important class of problems in computational
complexity theory; they are those problems that can be solved in polynomial
time by a nondeterministic algorithm and are at least as hard as any other NP
problem. I'd like to say that in Lojban, but I'm running into some problems,
hopefully not NP-hard ;)
Nondeterministic isn't the same as probabilistic. Both kinds of algorithm can
make random decisions, but the nondeterministic computer splits into several
copies of itself, each making one of the possible alternatives, while the
probabilistic computer just takes one alternative. For "probabilistic" I
could just say {cunso}, but "nondeterministic" I'm not so sure.
For "polynomial" I came up with {tefsujme'o}.
"Complete" here does not have its usual meaning, so I don't think {mulno} is
appropriate. It means that any other problem in NP can be converted into an
instance of an NP-complete problem in polynomial time, so they are the
hardest possible NP problems.
"Algorithm" could be translated by a fu'ivla {algoritmi} or a lujvo with
{tadji}.
The last problem (hopefully) is how to translate a compound of an initialism
and a word. Of the interlanguage links on Wikipedia, all (including Arabic
and Russian) use the letters "NP" except Serbian, which transliterates them
to Cyrillic, and Thai, which I don't know how to read. What should we do in
Lojban?
Pierre
To unsubscribe from this list, send mail to lojban-list-request@lojban.org
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
you're really stuck, send mail to secretary@lojban.org for help.