A Fibonacci complexity class

While working on a project that will come out soon, I developed an algorithm with strange asymptotic behavior. In one of the functions of the algorithm there was an arithmetic progression that had to be computed. It was not a big deal as it concerned small sets of numbers each time, at least that's what I thought.

So instead of using the formula of arithmetic progression, I just put a recursive function for it. Something like

int d = 1000;
public void progression(a){
    while(d>0){
         progression(a+1);
    }
    d--;

}
progression(0);

Where d was proportional to the input.

It worked fine, but it was slower than it should be. The reason was that the progression was computed quite a lot of times and eventually such a simple function was a huge computation burden. I was really surprised to discover that the asymptotic behavior of the algorithm could be described by the Fibonacci sequence.
So that, given n input the complexity of the algorithm was O(f(n)∙c), where f(n) is the n-th member of the Fibonacci sequence and c is constant.
After replacing the function with the formula of arithmetic progression the complexity became polynomial, thankfully. 

There are two remarks about all these.

An innocent, simple and naive function may become a problem. We have to be careful on how many times this function will be executed.

Although the first edition of the algorithm was not optimal, there comes the question. Could we define a Fibonacci complexity class? Perhaps even find problems in this class.

A function for the Fibonacci sequence

A very fast and easy function to compute Fibonacci sequence

import java.math.BigInteger;

public class main {
    int cnt=0; 
    public static void main(String[] args) {
        main m=new main();
        m.f();
    }
   
    public void f(){
        BigInteger a = new BigInteger("0");
        BigInteger b = new BigInteger("1");
        System.out.println("F("+cnt+"): "+0);
        cnt++;
        System.out.println("F("+cnt+"): "+1);
        cnt++;
        while(cnt<22001){
            BigInteger i = new BigInteger("0");
            i=i.add(a);
            i=i.add(b);
            a=b;
            b=i;
            cnt++;
        }
        System.out.println("F("+(cnt-1)+"): "+b);
    }
}

The output, the 22000th member of the sequence

F(22000):

23911151843088049549559913282124240747696450497332393096044892530723732731293925768111253903890731043326256888603201506944633327289997819833277130504901675470982030552507094162859800238507116975505854341394434948447565033026221210674687237739231690676803475798182981709459374260692436901977628581806475354563630219526845715243350120708966860434133018586240550140499321343707423004223534607204678776111145268537233116243802761082543246510402792429498707827152647989073216179648475243965598252066378230654130470829925986857896675242722600485435164105264916456225839778968745829788512608356363913804761755901467120731200188413083136579975059928902776220812920982189971242379916708698973621766751597334216368620508938142664716772647688988834270374687235249785796824594603884916806990714534340114784869357840251209972361365742785864148242067483656445079559019489390577428621648443326010160477386933121033620560251402766516093547505148407529090149475348773752540043271767234242084292100628738483524181221019416392799181393231992347653438406600914228647401007351836588160487756479497407968315031381589638689295174823322470087642165598672121365266344137564858444622711576081771078496641844937390545682240273855295137238355228099317669135050155578932164209299731907594076460356882408869295135953607469229651099120705693263857034687843626991261121860614751345764505435552449681904020194972948652249854216623551013979700998791070339585263264828474927294673678682855378403136525049646034651097985005523792023353505230733318315806249870620106255127740873138847984020791508370779261660785053242257951531507791170889410085082494377608208359506865872052269194573000651768246582561397589379054459666059728582161757153393761840155076715427874951737024712380325595601597280455609229448744861922777558470731225112774660744411373183007786591379470772659610931545615527361828527091916649882203801119543947473205919119948687005839582793430636346335172367632567614224230754519059566437786383250603562336173795450845023555052163775749567488680209929301733953771659440841851896501176310938478061013508743746794886211545059385083016686715569969754105054345618188437480456355103779247725818147048349484128145728116464124348995944145983490657741814168978702539394407772782423978914262812859165776960650497186523875998775018517623119052276070479290941716138770758463104282213404679330007239145717905126309090972993970782474750784981648644639346866248972640808995649185451943534239803644658697695716458521133485188727182407257352988202971646888599939358651008064484936913916373530359894095131542041397727523148718163746575229775017491009940588025249473123594753441211634435730001790835648327090911035577452758024952482629199328590011397832889757271508213625527057331090954110825073969299898958013994599894944208687850453500173980744223000760078898697128052192071515006870831715957325971845783409157683811011917636814704595836802955582938763983561376453999740428687093957605525631048148288024553370500665522100169024309239057322581866840037497559911574765827496593193700042249031389395129435568195231113075207830333318500469629193676005498811061550348234102052774122312886541766341471582469457347117636205703661078984515116258554803095676657019285090837775746036193164235341465548098904615127611062939206161346093617265405906367027661546845621356149559040798776562241563525511725505792648393371898115939776591096309370497408492873254883402409802564872039524422858633347863626333558155009162515951780107533626468012894434520530192845273457409548744656177387603307356149287599938730196582636274410931646393247886112418444661056857161146184933011078210524893794117348746892516723498126540948178477524603638775070638523850390891025039264400618873393052111880108096369408947789274041790558597294722651729924404836342862376149286822275330813331363925609055924677777163416615796764181780714265864396474084320765015608284585854217131086151555790325994153510435163207497453674171928909161205383175664268065518581620152617418382937870516278875447542815346729709387258529667056688675843466545834345387745629279011899890664127165078236901460104874038389111495950291594316779654469302636244158996341777359509518944948859542336178551804878882015290324970263731030303062802591853791022670735831866555863543199284768114955047509691099289344617944901044767695479022055197983956300649586454906832181127379710025435852700124842320460296470665284849646627146368239854763930002211169617338509922746447728861929093704279396632724922533039876469981523255796252507976652376398665656696184253857275835860915242223337528463584609575885682566329602411550875

Killing time while in quarantine

There are many posts in blogs and social networks these days about what some people do or what suggest to others to do while they are isolated in quarantine. Well, this is my suggestion.
Find a difficult and interesting open problem and try to solve it. Some problem that you may understand its definition but you and the rest of the world have no idea about its resolution. In computer science and logic good candidates are the famous NP vs P problem or the Continuum Hypothesis; of course there are numerous others.
Reading about the problem and working on any idea that you may have about it will not only be an interesting task but will probably make you learn something interesting and it will surely help you in killing time. Who knows, eventually you might actually solve the problem and gain fame and fortune.
In case you follow this advice here is another one on how you should approach it. If you want to solve an open long standing problem you have to think innovative and differently than everybody else. If thinking like everybody else and following the mainstream would be enough to solve the problem then it wouldn’t have been open as someone would have already solved it.

CONVID-19 coronavirus quarantine. A chance to promote e-conferences.

The quarantine that has been imposed to many parts of the world due to the spread of the CONVID-19 virus creates a lot of problems in transportation and in events like conferences. This may be a chance to reconsider the way that scientific conferences are organized. Although modern technologies of teleconferencing are used in a wide scale in education they are not used in conferences. So in parts of the world were the organization of gatherings is nowadays impossible, conferences have to be canceled.
A good alternative in all these trouble is simply teleconferencing, probably including an archive of video presentations and lectures. But if the scientific community will ever move to this direction there will be more benefits than just dealing with a temporary uncomfortable situation. Promoting teleconferencing and establishing a new type of e-conferences will make conferences open to a wider audience, not just to those people that make it to attend the event. Even without the quarantine, traveling to other countries and continents to attend a conference is not always an easy case and for many people is a difficult issue.
The demand for open science and data should not be restricted to the free dissemination of papers and preprints. In an era were multimedia flood the web and MOOCs are the latest trend in education, conferences should follow the same direction and become open platforms for exchanging ideas and interesting results in global scale.

Continuum Hypothesis and Uncountability

After setting the foundation on set theory by working on number sets and proving that the set R of real numbers is larger than the set N of natural numbers, Georg Cantor started working on a puzzling issue that was later called the Continuum Hypothesis. This deals with the following question “Is there a set of cardinality larger that set N and smaller that set R (the continuum)?”
Cantor believed that the answer to the question is negative but he did not managed to prove it and no one else did. So 150 years later this belief is formed as a hypothesis and it is still open, for most people.
Perhaps the most complete article on the hypothesis may be found here, it explains in details the whole issue its implications and the progress so far.
Researchers mainly use logic and axiomatic set theory on their attempts to prove the hypothesis. The research efforts focus on applications of the Zermelo-Fraenkel axioms with the axiom of choice; known as ZFC axiomatic system. The problem on this approach is that the hypothesis has been proven by Gödel and Cohen to be independent of ZFC. Since then, the scientific community has been divided in two parts. Scientists like Cohen believed that independence imply undecidability and the hypothesis has no answer. Others, like Gödel, believed that the ZFC system is not appropriate of resolving the hypothesis and some new system of axioms should be adopted.
This post is about some remarks that I have about the hypothesis and the ZFC application on it. The belief that ZFC independence results undecidability clearly implies that the ZFC system is universal on the sense that the properties of every possible set may be effectively described by the system. As ZFC is an axiomatic system and some of its axioms rely on intuition its universality should not be taken for granted.
For instance, the well-ordering theorem that is equivalent to the axiom of choice states that in every non-empty set there is one least element based on some property of the set. If we consider a set of uncomputable numbers how can we claim that any element of the set is the least element? It would be fruitful to investigate new axiomatic systems or try to provide stronger evidence about the validity of the currently used axioms.
Now let us suppose that the hypothesis is false and there is set H the cardinality of which lays between N and R. Set H is uncountable and its elements are uncomputable.
Set H is uncountable as it is larger than N. Considering the Turing machine model as a universal model of computation and as the set of all Turing machines is countable there are more elements in H than Turing machines so there are elements of H that do not correspond to a Turing machine and as a result they are uncomputable. There are uncomputable numbers in R as well and these considerations imply that a system or a theory that could be used to prove or disprove the existence of H should be able to handle uncomputable numbers and their properties.