Explication réductible du temps polynomial

Question

Ayez un ensemble d'exemples qui m'ont donné, mais je suis presque sûr qu'ils se trompent. Quelqu'un peut-il vérifier que ma compréhension de leur compréhension est correcte?

Si défini $ Y $ peut être résolu dans $ O (2 ^ n) $ et $ Y leq_p x $ alors $ X not in p $ c'est faux

Je pense que cela signifie que depuis $ Y $ est ne pas temps polynomial résoluble, et il est réductible à $ X $, alors x n'est pas le temps polynomial réductible. Cela a du sens pour moi, mais la déclaration se termine par un faux, comment est-ce?

Si $ Y leq_p x $ et $ X $ est résoluble en temps constant, alors $ Y $ est également résoluble en temps constant

Semble assez intuitif, si vous pouvez réduire $ Y $ À l'aide d'un réducteur polynomial, il doit également être résoluble en temps constant. Mais j'ai le sentiment harcelant que ce ne serait pas un temps constant depuis le temps polynomial> temps constant.

Dire que tu as $ Sort $ qui vérifie si la liste des INT est triée, alors pour tous $ X $ Nous avons $ Sriet leq_p x $

Je ne comprends pas du tout, comment le peut le $ Sort $ algorithme être réductible à tout $ X $, n'est-ce pas un peu trop farfelu?

Présumer $ Y leq_p x $, si $ Y $ n'a pas d'algorithme de temps polynomial pour le résoudre, alors il n'y en a pas pour $ X $ Soit

Je pense que cela implique que depuis $ Y $ n'est pas résoluble en temps polynomial alors ni l'un ni l'autre $ X $, mais n'est-ce pas faux? Le but de nous d'utiliser des réductions est-il de montrer que nous pouvons réduire l'un à l'autre qui a déjà une solution, traduisant ainsi la solution?