[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.