Definizione di Funzione appropriata

Nella definizione di funzione appropriata:

wsf0wxfohnmu.jpg

Qual è l'utilità del secondo punto e perchè è cosi importante in tutte le definizioni e teoremi successivi?

Esempi esplicativi di funzioni NON appropriate che violano il secondo punto?

Grazie mille! :D

Comments

  • MindFlyerMindFlyer Posts: 436
    E' importante perché serve in punti chiave di teoremi come quello della gerarchia. Tutti gli algoritmi "interessanti" hanno complessità in tempo e spazio che sono funzioni appropriate. D'altra parte, la teoria che vuoi costruire deve applicarsi agli algoritmi interessanti, e non t'importa nulla di quelli "insensati". Quindi ha senso restringersi a questa classe di funzioni, e succede che queste due ipotesi sono sufficienti per avere una teoria abbastanza ricca. Rimuovere le ipotesi fa effettivamente succedere cose strane (e.g., teoremi di Blum e Borodin) per funzioni che non hanno rilevanza pratica.

    Per quanto riguarda una funzione calcolabile monotona che viola il secondo punto, si tratta di un bell'esercizio.
  • MindFlyerMindFlyer Posts: 436
    Hint: considera un linguaggio E che appartiene a EXP e non a P (che esiste per il teorema della gerarchia). Puoi costruire una funzione monotona e calcolabile f(x) che non sia appropriata definendola opportunamente a seconda che x appartenga o no a E...
  • Scusa per la domanda.... Ma se considerassimo funzioni di misura strettamente crescenti invece che monotone crescenti, succederebbero dei casini nel teorema di gerarchia?
  • MindFlyerMindFlyer Posts: 436
    edited January 2017
    mikele_94 wrote: »
    Scusa per la domanda.... Ma se considerassimo funzioni di misura strettamente crescenti invece che monotone crescenti, succederebbero dei casini nel teorema di gerarchia?

    No, per niente. Siccome il teorema vale per tutte le funzioni appropriate, se si restringesse la classe delle funzioni appropriate il teorema varrebbe a maggior ragione. Inoltre, tutte le funzioni per cui t'interessa applicare il teorema della gerarchia, ovvero le solite [tex]n^k[/tex], [tex]\log^k(n)[/tex], [tex]k^n[/tex], e loro composizioni varie, sono strettamente crescenti.
  • MindFlyer wrote: »
    Hint: considera un linguaggio E che appartiene a EXP e non a P (che esiste per il teorema della gerarchia). Puoi costruire una funzione monotona e calcolabile f(x) che non sia appropriata definendola opportunamente a seconda che x appartenga o no a E...

    Ci sto ancora pensando, ma è legato al fatto che richiede complessità in spazio e tempo con il fattore [tex]f(|x|)[/tex] invece che [tex]f(x)[/tex] ?
  • MindFlyerMindFlyer Posts: 436
    No, stai pensando cose strane... :o
  • Gaspare FerraroGaspare Ferraro Posts: 44
    edited January 2017
    MindFlyer wrote: »
    Hint: considera un linguaggio E che appartiene a EXP e non a P (che esiste per il teorema della gerarchia). Puoi costruire una funzione monotona e calcolabile f(x) che non sia appropriata definendola opportunamente a seconda che x appartenga o no a E...

    Allora prendiamo per esempio:
    [tex]
    f(x) = \begin{cases}
    A & x \in E\\
    B& altrimenti \\
    \end{cases}
    \\
    \\
    E \in EXP \backslash P
    [/tex]

    Quindi dobbiamo dobbiamo scegliere A e B in modo che
    [tex] x_{1} \geq x_{2} \Rightarrow f(x_{1}) \geq f(x_{2})[/tex]

    e che sia complessità in tempo più di [tex]O( f(|x|) + |x| )[/tex] oppure in spazio di [tex]O( f(|x|) )[/tex]
  • Gaspare FerraroGaspare Ferraro Posts: 44
    edited January 2017
    proviamo con
    [tex]
    f(x) = \begin{cases}
    2x & x \in E\\
    2x+1 & altrimenti \\
    \end{cases}
    \\
    \\
    E \in EXP \backslash P
    [/tex]

    Questa funzione è crescente ( [tex]f(0) = 0 \lor 1[/tex], [tex]f(1) = 2 \lor 3[/tex], ... )

    Però controllare che [tex]x \in E[/tex] ha complessità esponenziale mentre [tex]O(f(|x|)+|x|) = O(|x|)[/tex] a meno di fattori costanti. Ha senso?
  • MindFlyerMindFlyer Posts: 436
    Ok, ci siamo (però scrivere le moltiplicazioni con * è veramente da ingegnere :s ).

    C'è solo una smagliatura alla fine, perché la non calcolabilità di f in tempo lineare si deve dimostrare in modo un po' diverso. In C&C più che mai bisogna distinguere tra il concetto di funzione e il concetto di algoritmo: un algoritmo calcola una funzione, ma una funzione (calcolabile) può essere calcolata da diversi algoritmi. Tu hai specificato un algoritmo per calcolare f che coinvolge la verifica che x sia in E. Però non è detto che per calcolare f si debba per forza fare questo controllo. Esempio banale: se non ci fosse quel +1 nella definizione di f, potresti calcolarla semplicemente raddoppiando x, anche se l'algoritmo dice di verificare se x è in E.

    Per concludere in modo preciso bisogna fare le cose "al contrario": dimostrare che se f è appropriata, allora E è calcolabile in tempo lineare. Infatti, dato un y, diamo in pasto un input di lunghezza y alla MdT del punto (ii) della definizione di funzione appropriata, la quale spara fuori in tempo lineare una stringa di lunghezza esattamente f(y). Adesso, sempre in tempo lineare, controlliamo se questo output ha un numero pari o dispari di simboli. Se sono pari concludiamo che y è in E, altrimenti concludiamo che y non è in E. Quindi abbiamo deciso E in tempo lineare, il che è assurdo per definizione di E.

    Nota che lo stesso discorso potevi farlo con la complessità in spazio, usando questa volta l'altro teorema di gerarchia e prendendo una funzione in EXPSPACE\PSPACE.

    Nota anche che tutto questo si regge perché il punto (ii) vuole che la MdT restituisca esattamente un output di lunghezza f(|x|), e non per esempio uno di lunghezza al più f(|x|), oppure O(f(|x|)), o altro. Non a caso, questa precisa caratteristica della MdT è usata nella dimostrazione dei teoremi di gerarchia.
Sign In or Register to comment.