Spiegazione riducibile del tempo polinomiale

Question

Avere una serie di esempi che mi sono stati regalati, ma sono abbastanza sicuro che abbiano torto. Qualcuno può verificare che la mia comprensione di loro sia corretta?

Se impostato $ Y $ può essere risolto in $ O (2^n) $ e $ Y leq_p x $ poi $ X not in p $ è falso

Penso che questo significhi che da allora $ Y $ è non tempo polinomiale risolvibile ed è riducibile $ X $, quindi X non è tempo polinomiale riducibile. Questo ha senso per me, ma l'affermazione termina con un falso, com'è?

Se $ Y leq_p x $ e $ X $ è risolvibile in tempo costante, quindi $ Y $ è risolvibile anche in tempo costante

Sembra abbastanza intuitivo, se puoi ridurre $ Y $ Usando un riduttore polinomiale, dovrebbe anche essere risolvibile in tempo costante. Ma ho la sensazione fastidiosa che non sarebbe tempo costante dal tempo polinomiale> tempo costante.

Dì che hai $ Ordina $ che controlla se l'elenco di int è ordinato, quindi per tutti $ X $ noi abbiamo $ SORT leq_p x $

Non lo capisco affatto, come può $ Ordina $ Algoritmo essere riducibile a tutto $ X $, non è un po 'troppo inverosimile?

Assumere $ Y leq_p x $, Se $ Y $ non ha un algoritmo di tempo polinomiale per risolverlo, quindi non ce n'è uno per $ X $ o

Penso che questo implichi da allora $ Y $ non è risolvibile nel tempo polinomiale, quindi nessuno dei due $ X $, ma non è falso? Non è lo scopo di noi che utilizzano riduzioni è dimostrare che possiamo ridurre l'uno all'altro che ha già una soluzione, traducendo così la soluzione?