6

This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of ...


3

A bit is, by definition, a binary digit, and binary means base 2. Base two is the most common model of computing, but it is not the only one. There is also analog computing, which is not that interesting to computer science. Ternary logic, on the other hand, does lead to some interesting theory. In that case, however, each digit would be called a trit. ...


2

The manufacturers of the computing hardware themselves are their own customers, and use supercomputing to approximatively solve a number of well-know and more obscure NP-hard tasks. One of the oldest and best-known is place-and-route, a short overview of electronic design automation reveals many more NP-hard tasks. Often the employed algorithms are true NP ...


Only top voted, non community-wiki answers of a minimum length are eligible