Los modelos resuelven menos problemas cuando un cambio estructural los vuelve NP-completos

Cuando un detalle estructural cambia un problema de resoluble en tiempo polinómico a NP-completo, ¿pueden los modelos de lenguaje adaptar sus soluciones a la nueva estructura computacional?

Las pruebas existentes no emparejaban estas clases manteniendo el contexto de los problemas lo bastante parecido, por lo que era difícil aislar esa pregunta.

Los autores crean P2NPCBench, un conjunto de problemas de programación pareados para evaluar si los modelos siguen un cambio estructural que convierte un problema resoluble en tiempo polinómico en uno NP-completo.

Los autores comparan problemas pareados de 12 familias. Cada pareja comparte un contexto, mientras que una característica estructural cambia si el problema es resoluble en tiempo polinómico o NP-completo.

Un enunciado solo cuenta como resuelto cuando una solución de Python generada supera todos sus casos de prueba.

En los 12 modelos, la proporción media de enunciados resueltos fue del 63.8% para los problemas de tiempo polinómico y del 35.4% para los NP-completos; cada modelo obtuvo una media más baja en estos últimos.

La comparación pareada respalda la existencia de una brecha de rendimiento asociada con el cambio estructural.

Los resultados abarcan 12 familias de problemas en inglés, problemas de las clases P y NP-completos, y soluciones en Python 3. Los enunciados se endurecieron frente a un panel fijo de cuatro modelos, hay versiones relacionadas dentro de cada linaje y cada modelo evaluado produjo una sola muestra codiciosa. Estos resultados no establecen el rendimiento fuera de ese ámbito.