Transformation

Happy new year.

Just a random passage appreciating one of the common techniques...


While my research is going on with a stylish way, I found more interesting stuffs concerning computational complexity.

Transformation is really a magical topic in mathematics. In secondary school you learn some kind of functions, and they are actually a transformation of numbers. If there were two number world both R, one being x and one being x^3, two numbers from each of the world can be equivalent given a function linking them.

Why not x^2? Well, you've learnt the concept of bijectivity in high school. If the two worlds can't be linked with a bijective function, its inverse will not be equivalent to the original one.

If there are something that are equivalent, then some of them will deliver difference in strength? Yes. f(x) = x^2 (R->R) is stronger than g(x) = sqrt(x) in terms of f 'shows more than what g does'. g can be well inversed to show half of f but the converse isn't true.

Strength and inversibility can be assigned into another system with a more significant meaning --- the system of theories.

Theorems are composed based on previous theorems and axioms. Gradually and eventually the whole subject called mathematics is constructed.

Theorem can be further decomposed by logic. Theorems are in forms of 'if A then B' we can rewrite it in forms of 'A -> B'. The inverse might not be true (because the theorem does not state it). If the condition and result can be reserved in the theorem we call those situations as equivalent which is 'A->B and B->A'.

'A and B are equivalent' is of course stronger than 'if A then B' because there's an extra condition than what the second one could describe. That again induces the difference in strength. A statement x is stronger than statement y if 'x->y' is TRUE but 'y->x' is FALSE.

Many theorems in distinct field could be equivalent with some amazing imagination and superb proofs. One of the famous example is the FLT: Fermat's Last Theorem. It's linkage with elliptic curve has been a key towards the proof of it. Another example, which is an open problem, the Riemann's hypothesis has quite a number of equivalent statements, like the lindelof's hypothesis --- both of them describes the Riemann zeta function's behavior especially at the critical strip Re(z) = 1/2. Two statements hypothesizing very distinct aspect, but they turn out to be equivalent.

Transformation is not restricted to advanced mathematics and my research field has been inspiring me a lot. In computational complexity there are a set of problems labelled NP-complete, is the 'hardest problem' in the set of NP problems, which implies that the answer, if provided towards the question, can be verified in a very fast time. It implies the hardest --- but not only a single question. It has been proved that more than 1000 problems belongs to the category. They are the hardest --- and all have the same difficulty.

Proving the first one has been difficult (a 'by definition' approach based on Turing machine but the rest of them base on transformation from one to another, and by such a way many of the problem can be handled in a more efficient and systematic way.

At the end of the day, all of the above seems to be sort of rubbish talks, but we shall appreciate the beauty of Nature --- one tool applying in many fields with a shit loads of symmetry and simplicity, just like the rest of the science of what we have already discovered.