Procedure efficaci e problema P vs NP

Question

Se, supponiamo, P non è uguale a NP. L'implicazione di questa affermazione è che non esiste una procedura efficace per risolvere un problema difficile; Tuttavia esiste una soluzione accettabile S. Ho seguito due domande esplicite:

1. Se non è possibile fornire una procedura efficace che produce una soluzione, in che senso è effettivamente a soluzione? Questo sfida la definizione formale di soluzione? Suppongo che una procedura efficace sia equivalente a una prova.

2. Se non esiste una procedura efficace per arrivare a una soluzione accettata, ciò implica che la soluzione non è una conseguenza sintattica del problema. Secondo la definizione formale, le conseguenze sintattiche sono equivalenti a una procedura efficace. Se la soluzione a un problema difficile non è una conseguenza sintattica del problema, che cos'è?