1
$\begingroup$

Question: What is known about the role that binary representation of data plays in algorithmic complexity theory?


I define "analog representation of data" loosely as any method of representing data which is not a sequence of 1's and 0. A more precise definition would be nice to have obviously. The basic idea is that an analog representation of data contains additional information beyond what is contained in a binary representation.

A very trivial example of an "analog" representation of the natural numbers is to label all the primes $p_1, p_2, p_3 \cdots$ and then represent numbers by their prime factorization, instead of in binary form. It is obvious that with this representation of numbers, the problem of factoring large numbers is of polynomial complexity.

Less trivially, according the Shor's Alogirithm, if we represent numbers using an analog physical system (in this case, using quibits instead of bits), then it's possible to factor large numbers in polynomial time as well.

The natural conclusion to draw is that the choice to use binary or not for representing data likely plays an important role in determining if a given problem is in P or NP, and one would think that in order to prove P is not equal to NP it would be required to use the assumption that data is represented in a binary way at some point.

Sorry for the open ended question. Any and all feedback is very much appreciated. I am getting out of my comfort zone here and was unable to find much help using google.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ But of course, if you represent numbers "by their prime factorization" then incrementing a number becomes a possibly NP operation. $\endgroup$ – dxiv Nov 8 '16 at 23:40
  • $\begingroup$ If you write integers in unary ($n$ becomes $n$ vertical strokes) then prime factorisation is polynomial in the number of digits, but you do not make it faster $\endgroup$ – Henry Nov 9 '16 at 3:31
1
$\begingroup$

"Binary or not" is not the central issue. Well designed data structures can speed up classical computations, but underneath those data structures it's all bits. What quantum computing does is to allow for massively parallel computation, thus problems that may be NP on a classical computer can be P on a quantum computer.

Here's the start of wikipedia's discussion:

Quantum computing studies theoretical computation systems (quantum computers) that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data.1 Quantum computers are different from binary digital electronic computers based on transistors. Whereas common digital computing requires that the data are encoded into binary digits (bits), each of which is always in one of two definite states (0 or 1), quantum computation is analog and uses quantum bits, which can be in an infinite number of superpositions of states.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The reason the algorithm computes in polynomial time according to wiki is "the ability of a quantum computer to be in many states simultaneously". I presume this is what you mean. I would characterize the situation as follows: you take a physical system and measure its properties while changing some physical parameters, and then plug the result of the measurement into a formula to compute the answer to some problem. This is all very non-mathematical is my point. My question is motivated by the desire to understand this phenomenon of non digital data in a more precise mathematical way. $\endgroup$ – Matt Calhoun Nov 9 '16 at 0:04
  • 1
    $\begingroup$ @MattCalhoun There is a sound mathematical model for quantum computing. That's separate from the question of how you build a quantum system that implements that model. The situation is similar for classical computing: the mathematical model is independent of the physics of transistors, or the physics of Babbage's analytical engine. $\endgroup$ – Ethan Bolker Nov 9 '16 at 0:16
  • $\begingroup$ That makes a lot of sense, thanks for the great comment. I definitely need to study the mathematical model of quantum computers a lot more closely than I have. In your answer you said "underneath everything its all bits", but I would assume that in the mathematical model of quantum computers numbers are represented by quibits and explicitly not by bits. Would it be fair to say that in this model, whether you represent numbers in "binary or not" actually is the central issue, and that underneath its not all bits? $\endgroup$ – Matt Calhoun Nov 9 '16 at 0:47
  • $\begingroup$ @MattCalhoun Probably, but I'd call it representing data rather than numbers. That said I've now reached the limit of what I actually know about quantum computing. $\endgroup$ – Ethan Bolker Nov 9 '16 at 0:50
1
$\begingroup$

The term "analog", in data communication, refers to continuous functions of time, as opposed to a discrete-valued one. Using that term for representing the integers by their prime factorizations conflicts with the practice.

If you are trying to ask whether we lose information (accuracy) by going from the uncountable (the reals) to a countable subset, then for all practical purposes we do not: the rationals are dense in the reals.

Further, I don't think the polynomial time achievement in Schor's algorithm is in how we represent numbers. It's in the quantum parallelism.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Maybe analog was a poor choice of words. I got this language from Von Nuemann's book The Computer and The Brain, which has a long discussion on the important distinction between digital and analog systems. $\endgroup$ – Matt Calhoun Nov 8 '16 at 23:42
  • 1
    $\begingroup$ In that case, you might find Feyman's Lectures on Computation on the mark, as it discusses the very questions that seem to interest you. $\endgroup$ – avs Nov 8 '16 at 23:44
  • 2
    $\begingroup$ I have read that book front to back twice, it was how I first got interested in Turing machines. I also highly recommend this book to everyone. $\endgroup$ – Matt Calhoun Nov 8 '16 at 23:45
  • $\begingroup$ I was not asking whether we lose information by going from an uncountable to a countable subset. Mostly I was hoping there might be some references or results that people know about which deal with the role that binary representation plays in algorithmic complexity. I respectfully disagree that the polynomial time achievement in Schor's algorithm is not a result of avoiding a binary representation, since if numbers were represented as bits instead of quibits, the quantum parallelism would not be possible, unless I am misunderstanding something. $\endgroup$ – Matt Calhoun Nov 9 '16 at 0:26
  • $\begingroup$ I see. Well, qubits are binary as well, being probability spaces with two ouctomes. What distinguishes qubits from the bits is the probabilistic nature, as I understand it (I am no expert). Also, what is your opinion of this quote from the Wikipedia article on Shor's algorithm: "The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.". $\endgroup$ – avs Nov 9 '16 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.