ACE ENGINEERING ACADEMY

THE ORIGINAL ACE ENGINEERING ACADEMY

**(ON-LINE EDUCATION, OUTSOURCING HRD & GATE/IES)**

gateguru@gateguru.org

GATEGURU.ORG

HYDERABAD, TELANGANA 500076

ph: 914027174000

alt: 09052345550

gateguru

**[Draft--Subject to modification]**

**HOBBYIST STUDIES TO WHILE AWAY TIME **

++++++++++++++++++++++++++++

**(Most likely situation)**

THE MAGIC OF THE Euler-Mascheroni CONSTANT

*SPECLATIVE RAMBLINGS*

*LEADING TO P=PSPACE*

THE REALITY OF THE CONCEPT OF AN ORACLE

PENGUIN’S DISCOURSE ON

*In the Theory of Computation the concept of an oracle is used. It is based on the idea that one can have oracles or soothsayers who are modeled by computational devices that can predict the outcome of a computation instantly i.e in deterministic polynomial time, wheras the computation itself may take eons i.e. exponential or super exponential time.**Consider a soothsayer like the famous legendary Nostradamus who predicted many things in “deterministic polynomial time” i.e. in his lifetime wheras it has taken decades or centuries for the events to actually take place. In all civilisations and cultures we have these prophets and soothsayers. *

*A legendary prophet is Hiawatha who predicted that the white gods will come over the ocean some day and liquidate his people and occupy their lands.*

* The Flood and Fifth Horseman have been predicted in many cultures. They may take decades, centuries of eons of time to actually occur but have all been predicted in the lifetime of the soothsayers concerned. *

*A recent astrologer has been Jeanne Dixon who in her lifetime predicted in “deterministic polynomial time” events which may take decades of centuries to occur. The science of astrology in many cultures actually deals with the concept of prediction in deterministic polynomial time events which may take a lifetime to unfold. *

*In the Indian environment which is used to multivalued logic the traditional science of astrology is respected culturally but decried in formal education which is influenced by Western thinking. So people can comfortably believe in it and at the same time not believe in it! This science has been decried in other cultures sometimes on religious grounds.*

* The famous Joan of Arc of Gaul used this concept of being able to forsee in deterministic polynomial time events that took days, years or decades to unfold. However as was the fashion those days she was rewarded by being burnt alive at the stake. This was the routine fate of countless number of witches and wizards who dared to foretell the future in deterministic polynomial time though the event itself may take an exponential amount of time to trace out step by step.*

*The rise and fall of dictators, warlords and warmongers in seemingly peaceful cultures have been predicted by many soothsayers over the centuries in deterministic polynomial time, only they prophecy was justified after decades, centuries or eons of time.*

*The Great Mathematician Gauss remarked that the end result was clear,(deterministic polynomial time), only working to it was difficult (exponential number of steps).**The legendary Michelangelo has remarked that to carve out the statue of David is easy. He could see the result in the block of marble, (in deterministic polynomial time), the job was to remove the extra pieces of marble,(exponential number of steps).**In all walks of life we have people gifted with intuition/Vision who can forsee the end result in deterministic polynomial time only the event will occur days, weeks, decades or centuries later on. Such people are either highly prized in the society and culture they live in or they may end up with the rope and the stake!**Many centuries ago Francis Bacon foresaw the coming of air travel. Legends report that more than a thousand years ago the coming of Mahatma Gandhi was predicted by a legendary soothsayer in south India.**Over the last three score years and ten many super-programmers have come along. One of them has remarked that to code a bug free complex program was easy. One could see the result, (in deterministic polynomial time), then one removed the fuzziness and wrote out the code, (in an exponential number of steps).**Royalty, Nobility and Mandarins in all cultures and civilisations have always consulted astrologers and soothsayers. All of them have not been hanged or burnt alive which means there is some substance that some of them were able to successfully predict in deterministic polynomial time events that took an exponential or super-exponential time to unfold.*

**The classical science of Computational Complexity is built on the assumption that to represent an integer n one needs log(n) bits using the Arabic Positional Notation. Along with this if we use the Euler-Mascheroni constant and its properties we can tackle integer factorization and the P=NP problem in deterministic polynomial time.**

** We do exhaustive search in deterministic polynomial time in a Heffalump Table of Order One where the number of rows in the table is O(2^n^k) and the number of columns is O(n^l) for integer constants k and l, given that the size of the problem is n. The representation of an integer in the range 0..O(2^n) by O(n) bits is renamed as the Roo Number Representation of Order One.****An integer in the range 0..O(2^2^n) by O(n^2) bits is called the Roo Number Representation of Order Two. We can construct a Heffalump table of Order Two which has O(2^2^n^b) rows and O(2^n^a) columns, for some integer constants a and b, and uses an associative memory based on the Roo Number System. An exhaustive search in this double exponential table in deterministic polynomial time using properties of the Euler-Mascheroni constant resolves the fact the P=PSPACE. Note that this double exponential size table need not be constructed, it is a virtual table and only a polynomial number of entries indexed need be determined. ****When the Roo Number Representation is repeatedly used on itself we will have a Roo Number Representation of Order P, for some P. From this we know a Heffalump table of Order P with an associative memory exists only the construction may not be effective. An exhaustive search in deterministic polynomial time using the properties of the Euler-Mascheroni constant resolve the fact that Presburger arithmetic can be resolved in deterministic polynomial time provided the Heffalump Table is not counted, else it takes double exponential time. ****An exhaustive search in a Heffalump table in deterministic polynomial time consists of a Solver who uses existential nondeterminism to choose a row of the table. This is done having an existential Pooh-Tigger cake distribution race. What the Solver chooses is verified by a Verifier who uses universal nondeterminism. This is done by starting an universal Pooh-Tigger cake distribution race. The Solver will be able to successful choose a solution provided Tigger is able to place himself exactly half a house ahead of Pooh in the cake distribution race. In a Pooh-Tigger cake distribution race resonance occurs when Tigger is exactly half a house ahead of Pooh.**

**In principle even if an event takes Ackermanns function or more to unfold the outcome can be determined in deterministic polynomial time assuming the Heffalump Table is available. Only the construction of the Heffalump Table and the determination of the exact Order of the Roo Number system to be used may not be constructive, we only know it exists.**

**Consider a game like nxn chess. It is clear that one of the three choices must result at the end of all possible games. Either white will win, or black will win or it will end up in a draw. This problem is in PSPACE and can be expressed as a problem in AP. One can use a Heffalump Table of Order Two and in deterministic polynomial time predict the outcome. The game itself may have an exponential number of moves and take eons of time to unfold.**

**In the area of Formal Verification the use of the QBF problem is found. This is in PSPACE and so the decision problem can be solved in deterministic polynomial time but the steps involved to fully trace out the solution may be exponential and take eons of time to list out in detail.**

**HOBBYIST STUDIES TO WHILE AWAY TIME**

**THE ROO-POOH-TIGGER STUDIES AS OF JUNE 2018**

+++++

*ENTERTAINMENT*

**(BEYOND GATE)**

(The magic of the Riemann Hypothesis applied to the harmonious interaction of competing and cooperating vanilla weighted finite Harmonic Series using the mysterious Euler-Mascheroni gamma constant which allows nondeterminism of all types to be tractably tackled by the traditional von Neumann computer for all problems of practical interest)

These studies have yielded the strange results that P=AP=NP=PSPACE (most likely) & that it is possible to better in space requirements the Arabic positional representation of an integer. The results have always been suspected by most people to be valid though as a remote possibility as they are disturbing. These results may not be generally acceptable and the student should NOT use them in formal/informal training/education programs. The student is advised to follow the standard texts and accepted results especially in examinations anywhere in the world. In any case it will take a long time for the results to be fully verified and still longer time, maybe decades, for them to be tolerated and fully accepted!!

**++++++++++**

**+++**

**++**

**+**

**THREE RESULTS**

1. The Roo Number System.

An integer n represented in the Arabic Positional Number System is bloated up to an enormous size using error control coding over deterministic controlled channels where the Shannon Limit does not apply. Then it is collapsed by a refereed NP-complete problem to a succinct size which is functionally less than log(n). It is possibe to recover the original integer without any loss from the collapsed representation. This works for all integers beyond a certain basic size.

2. The Pooh-Tigger race.

All types of nondeterministic behaviour lend themselves to simple explanations. Nondeterminism is merely practical deterministic exhaustive search using Pooh-Tigger races which are based on the Harmonic Series and the mysterious Euler-Mascheroni constant.

The search for an element in an exponential amount of data in deterministic polynomial time is the key to the solution. In the case of Existential nondeterminism Tigger will be exactly half a house ahead of Pooh when there is success. In the case of Universal nondeterminism Tigger will never be exactly half a house ahead of Pooh. Both types of exhaustive search in data of exponential size take only a deterministic polynomial amount of time. Thus it is possible in principle to simulate in deterministic polynomial time alternating Turing machines for the QBF and context-sensitive recognition problems by Pooh-Tigger races. This allows the conclusion that

**P****=AP=NP=BQP=co-NP=ZPP=IP=PSPACE=****P**

(most likely)

3. The Riemann Hypothesis demystified.

The Riemann Hypothesis lends itself to a simple explanation with the Pooh-Tigger races. A zero of the Riemann zeta function occurs when Tigger is exactly half a house ahead of Pooh in a Pooh-Tigger cake distribution race refereed by Piglet using the Piglet Transform!! A zero corresponds exactly and uniquely to a pair consisting of a composite integer and one of its factors.

++++

*ENTERTAINMENT*

**(BEYOND GATE)**

(The magic of the Riemann Hypothesis applied to the harmonious interaction of competing and cooperating vanilla finite Harmonic Series using the mysterious Euler-Mascheroni gamma constant which allows nondeterminism to be tractably tackled by the traditional von Neumann computer)

*COMMON SENSE AND NONDETERMINISM*

The definition of a time or space bounded nondeterministic device D that is colorful is that the machine makes copies of itself for every choice of move in a state. The copies make copies of themselves for every choice in the next move and so on. If there is a path from the initial state to the final state the machine accepts else it rejects. This is what we will call Existential nondeterminism. If we demand that all paths end up in accepting states then we have Universal nondeterminism. We can end up with optimisation problems like choosing the shortest path or the longest path to a final state. The behavior of the device D can be represented by a tree T, where the root is the start state and the choices make it go to then next level. If all the leaves are accepting then we have Universal nondeterminism, if one of the leaves is accepting we have Existential nondeterminism. The case of the shortest path or longest path determination can be done by converting the optimisation problem to a decision problem.

The tree may have an exponential number of leaves. However we can use exhaustive search in the leaves to determine if an accepting or rejecting state occurs. We start a Pooh-Tigger cake distribution race, use the Piglet Transform and the Lumpy function and if D is T(n) time bounded and nondeterministic we need only determistic time T(n)^k, k some constant, to determine the answer. So nondeterminism is not some surreal thing. It merely says that a nondeterministic device has the capability of performing an exhaustive search in an exponential number of elements in deterministic polynomial time. This is the magic of the Riemann Hypothesis applied to interacting finite Harmonic Series and using the mysterious Euler-Mascheroni constant.

*It is possible to make the traditional concept of bounded nondeterminism interesting by relating it to myths, legends and folklore of the world. Every culture has stories on the existence of supernatural beings. We have Jinns, Druids, Kami, Asuras, Rakshasas, Goblins, Fairies, Demons etc. etc. These characters have the capability of making multiple copies of themselves all acting in parallel. If one copy succeeds the Demon succeeds in the case of Existential nondeterminism. All the copies of the Demon must succeed for Universal nondeterminism. We have the concept of cloning a device in modern times. This concept is useful in making nondeterminism userfriendly in agrarian and pre-agrarian societies.*

However it turns out we do not need any supernatural beings. A nondeteministic device is smarter as it can in deterministic polynomial time search for an item in an exponential sequence of items. It is able to find a needle in a haystack! This is merely a property of binary search using the magic of the Euler Mascheroni constant!

+++++

KANGA SPECULATES QBF PROBLEM IS IN P

So far nobody had any idea how to tackle exhaustive search or make nondeterminism tractable in a computable exponential sequence of items. The Pooh-Tigger cake distribution races make both of these concepts tractable. This is enough to tackle NP-hard problems. We can tackle problems in co-NP, integer factorisation, discrete logarithm, elliptic curve discrete logarithm, N-queens problem, graph isomorphism etc. by these concepts and show that they are all tractable problems.

However it seems difficult to get some simple solution for the problem P=PSPACE. To tackle the QBF problem and show that it is in P is not easy and that is what Pooh and friends plan to do, though at a slow pace. So far they tried crossing sequences, multiple recursive Pooh-Tigger races, Solver:Solver-Verifier:Verifier triples etc. All these suffered from the Tom and Jerry syndrome and turned out to be 'howlers' and wrong. As expected one has to expect the TOM AND JERRY SYNDROME. So it will take a long time to find the solution and much more time to verify it and make it acceptable!

Gopher and Eeyore have come up with a QUICK AND DIRTY method to resolve the context-sensitive recognition problem in deterministic polynomial time that merits consideration!

The use of oracles realised with exhaustive search seems to be the solution!!

At present it is still a problem that is left to the reader!!!

++++++

+++++

We will solve the context sensitive recognition problem in deterministic polynomial time.

A table is created with a double exponential number of rows and and an exponential number of colums. The entries in a row of the table is a puported derivation with the sentential forms in sequence in a row. The strings in the rows are ordered lexicographically. In a derivation a setential form cannot repeat without looping and this places a upper bound on the columns of the table.

A Solver of the problem nondeterministically using existential nondeterminism selects a correct purported derivation from the rows. This choice is handed over to a Solver-Verifier who uses universal nondeterminism to see that the purported derivation is in order, as per the rules of the grammar.

To simulate the Solver two Pooh-Tigger races are needed as the rows are double exponential in number. One makes a polynomial number of probes giving exponential chunks of rows and the other makes a polynomial number of probes in an exponential chunk to the rows. These races implement existential nondeterminism. To simulate the Solver-Verifier who steps through the columns a Pooh-Tigger race is created which implements universal nondeterminism. The Solver Verifier makes a polynomial number of probes into the columns.He hands over two adjacent columns to the Verifier. The Verifier checks that the successor sentential form can be obtained from the preceding one. He also checks the starting and ending sentential forms. The verifier takes a polynomial amount of time.

The Solver's Pooh-Tigger races demand that Tigger be exactly half an house ahead of Pooh in case of success. The Solver-Verifier will find that Tigger can never be exactly half an house ahead of Pooh for a successful derivation.

The Solver and Solver-Verifier take only a polynomial amount of time to put the results of the polynomial number of probes together.

The total time is deterministic polynomial time complexity.

So context sensitive recognition is in P.

So P=PSPACE.

GATEGURU.ORG

HYDERABAD, TELANGANA 500076

ph: 914027174000

alt: 09052345550

gateguru