|
irreversible
This is not exactly a software related question, but it could be considered to fall under "computer science" through math.
Anyway, is there such a thing as irreversible operations? What I mean by that is you can go in one direction, but cannot come back to where you started from. I have a few I can think of: one-way hash functions are one such thing. I think the modulo operation is one way as well. Due to the wrap-around effect, one can't always trace back where one came from.
Do you guys know of any other?
irreversible
Sunday, May 9, 2004
Any non-invertible function is "irreversible"
.
Sunday, May 9, 2004
Lots of things are one-way. You could simply take a number, multiply by zero, and then ask someone to retrieve the original number. But, more to your point:
bitwise and / or / xor
bitwise shifts
Ankur
Sunday, May 9, 2004
The trignometric functions are irreversible if you use them over the domain of real numbers. For example, if you look at the sine function, you will find that f(x) = f(x + 2*k *pi) for all integer values of k.
trig
Sunday, May 9, 2004
A more proper word for this is one-to-one, don't you remember your high school algebra and the "horizontal line test"?
Roose
Sunday, May 9, 2004
Any function where a loss of information occurs. More exactly, any single operation where a loss of information occurs within a given context.
For a or b = 0 you know that both a and b were 0, for a or b = 3 you don't know which was which. The JPG and MP3 compressions are irreversible on the bit level, while they are meant to be "reversible enough" on the human level. A cryptogaphic hash is irreversible when the original data is lost; it is reversible "the other way around" when you use it to identify a given file.
Thus I suppose the irreversibility of a function is defined within given circumstances; The or-operation is it for the general case with the 0-result as a special case.
Holger
Sunday, May 9, 2004
Ehm... XOR is reversible! since:
(a XOR b) XOR b = a
(so more like... XORring with a particular constant is reversible)
If you're looking for general examples, anything where you end up with less bits than you started with is obviously not gonna be reversible.
Phrasing that mathematically, any operation where the cardinality (size) of the image is less than that of the range fails to be 1-1. Neat thing is 'cardinality' is defined especially so that statements like this work for infinite sets aswell as finite ones (although admittedly computer science is mainly interested in the finite ones)
Read up on some basic set theory, bijections, surjections, one-to-one mappings, etc. It's really not hard stuff.
Matt
Sunday, May 9, 2004
Google on "NP Complete"
Should answer your question at a fundamental level *and* keep you busy for the rest of the day.
Or you'll have a psychotic episode. YMMV.
Philo
Philo
Sunday, May 9, 2004
What the hell does NP completeness have to do with a function being one-to-one?
Roose
Sunday, May 9, 2004
format c:
TomA
Sunday, May 9, 2004
Isn't NP completeness about being able to traverse an operation in either direction with equal ease?
OP gives hash functions as an example of irreversibility. But a hash function is NOT irreversible - just test text against the hash until you find a match. However, it is not *easily* reversible - P!=NP, as far as we know.
In fact, dwelling on it a bit, NP Completeness is the exact answer to his question.
Philo
Philo
Sunday, May 9, 2004
Its been a long time since the computing theory lectures, but I though NP vs P was about whether you could find the *optimal* solution to a problem with a polynomial time algorithm (vs an exponential one). Classic case is the travelling sales man problem.
I don't see that it has a lot to do with reversibility ... though I think there are some cryptographic protocols that rely on certain problems being NP complete and hence unsolvable in a sensible amount of time given current technology (ie. they are irreversible for all practical purposes).
Rob Walker
Sunday, May 9, 2004
and I mean domain, not range. doh.
Matt
Sunday, May 9, 2004
Thats one of the differences in computers vs math.
Computers have memory buffers,
i.e. bitwis or multiply by 0 are irreversible, only if you didn't bother writing down the original in some other part of memory.
The only truly irreversible things arent operations on data but operations on system state where the system is out of your control:
i.e. you have drop but not creat table privilages on a table in a database
The Artist Formerly Known as Prince
Sunday, May 9, 2004
Rob - that's the point. The optimal solution *is* "the" solution. And there's no easy way to find it. But once you've found it, it's trivial to prove that it's the right answer.
The cryptography problem is factoring a number into its two prime factors. To find the factors (as of today) your only option is trial and error. But once you've got two factors, it just takes one calculation on a big calculator to prove it's the right answer. Again, easy function one way, almost impossible the other.
If you have a hash, you can run text through the same hashing function until you get the same hash; but once you have it, then no problem to run it through and prove that's the solution.
It's all about a problem being childishly easy to solve in one direction, but impossible for the largest computers in the world to solve in the other direction.
In other words, the problem is irreversible (or nearly so)
Philo
Philo
Sunday, May 9, 2004
Brush your twice a day and you will have your answer ;)
Any dynamic system is _irreversible_. Entropy increases. Add quantum entanglement to it and even time reversal is ruled out. Scrambled eggs. For a simple demonstration, take this equation. Email me for the XL Sheet, should you want it.
y = Ax(1-x), where A is an arbitray constant.
In a spreadsheet, iterate it over a 100 times. Have the value of A ranging from 2.5 to 4 by 0.01 increments in the columns. Set x = 0.1 for each column and iterate for each column. Imagine the graph of the values and then plot the results. Look at the graph. Chaos, in its true mathematical sense. The function is chaotic, i.e. sensitive to initial conditions, in this case, the value of the constant A.
Take any number in the 3-3.5 range of A, no amount of reversing the iterative process will give you the precise value of A for that number, however fine you increment A in the system.
My point is any mathematical construct can be made irreversible by incorporating an arbitary constant combined with a self-referential iteration.
KayJay
Monday, May 10, 2004
Actually, Philo, a hash function is irreversable since it involves a loss of information.
If you find a stream that hashes to the original hash value there is no way of knowing if this is the original stream or simply another stream that coincidentally hashes to the same value.
If you start adding conditions to what the contents of the stream can be (i.e. no more than 2^16 bits long, UTF-8 encoded, valid Finnish text, etc.) then the combined process of hash function plus constraints could be reversible but not the hash function alone.
Eudoxus
Monday, May 10, 2004
Then I'd have to clarify both the question and the answer...
Any equation is irreversible if different operands can yield the same result. If a result can only be the result of a unique operand or set of operands, then the issue becomes one of NP-completeness.
BTW, given this issue, doesn't that make addition irreversible? Sure 2 + 2 = 4, but so does 1 + 3...
Philo
Philo
Monday, May 10, 2004
> Rob - that's the point. The optimal solution *is* "the"
> solution. And there's no easy way to find it. But once
> you've found it, it's trivial to prove that it's the right
> answer.
This applies to some problem: e.g. factoring, but isn't generally true of NP problems.
For the travelling salesman problem there is no way to prove that an answer is the right answer short of an exhaustive search of the solution space.
Rob Walker
Monday, May 10, 2004
> BTW, given this issue, doesn't that make addition
> irreversible? Sure 2 + 2 = 4, but so does 1 + 3...
I think to be meaningful the definition of irreversibility must be restricted to a single unknown. a+b = c is reversible as long as you know any two variables.
I seems we've established that many functions are irreversible (multiplication by 0, modulo, trig functions, etc) but they aren't very useful.
To be useful the domain of output values of the irreversible function must be very large so that 'collisions' are rare.
Rob Walker
Monday, May 10, 2004
It's not so much that you can only work with one unknown. An operation is reversible if it is one-to-one (or one-to-many but one-to-many mappings aren't too useful in this context). f(a,b) = a + b is not one to one so it is not reversible but if b is constant then f becomes one-to-one and is reversible even if we don't know anything about the constant's value.
Of course, from a practical point of view in order to reverse it we need some more information about the domain of a. For example if a is one of a series of latin characters in an english language document encoded using f(a) = a + b mod 26 for some constant b then it is trivially reversible even though we do not know a or b.
This is where P or NP complexity come in. If your reversible function is only P complex then reversing it becomes relatively easy.
Eudoxus
Monday, May 10, 2004
Thank you all for your feedback. I am too familiar with the technical terms but what I meant by "irreversible" is any operation that is hard to trace back. A one-way hash works nicely since it does a many-to-one kind of mapping. Trig functions work nicely too since they are periodic.
I am not so sure if logic operations really qualify as irreversible. If you don't know what your inputs were, I guess they do qualify, but they are not exactly what I was looking for.
I'll check out "NP Completeness" and see if it helps.
Once again, thanks!
irreversible
Monday, May 10, 2004
No, I think you are conflating two distinct ideas.
Most people are speaking of "reversing" a function as in "given the output of this function, determine its input".
To make it fancy (and precise) -- A function maps from the domain to the range. A function is "reversible" (in your parlance, the real mathematical term is 1 to 1), if given any member "a" of the range (a set), you can uniquely determine a member "x" in domain (also a set) where f(x) = a.
NP-completeness has to do with algorithmic complexity. This has nothing to do with 1 to 1 functions. Functions in math are not the same thing as functions in programming. A function in math has no algorithmic complexity. The sin function by itself does not have any complexity. It is simply a definition of what input goes to what output. This says absolutely nothing about how it is calculated.
Indeed, there is no way to compute sin exactly on a computer, since the domain and range are reals. A computer can only represent rationals, which are approximations to real numbers. So there a dozens of implementation of an (approximation of) the sin function, each with its own algorithmic complexity. Thus the sin function has no inherent complexity itself.
I think what you are thinking of is that part of the definition of NP-completeness is that given the result of a given run of the algorithm, it is easy (computationally tractable) to verify if it the result is correct or not. In the case of the satisfiability problem (the canonical NP-complete problem), all you do is take the output of the algorithm and plug it back in to the boolean formula (the input), and you can tell if the algorithm produced the correct result.
This has nothing to do with taking the output and determining the input. It is about verifying the correctness of the algorithm used to determine the input.
If you are looking for information on "reversible" or 1-to-1 functions, then it will probably only confuse you to study NP-completeness and other complexity theory. Functions are not algorithms, in math.
Roose
Monday, May 10, 2004
 Recent Topics
Fog Creek Home
|
