"" "ਕੰਬਿਨੇਟਰੀ ਸਮੱਸਿਆਵਾਂ ਵਿਚ ਸੁਧਾਰ" ""
1972 ਵਿੱਚ, ਰਿਚਰਡ ਕਾਰਪ ਨੇ ਇਸ ਵਿਚਾਰ ਨੂੰ ਆਪਣੇ ਇਤਿਹਾਸਕ ਪੇਪਰ, "ਕੰਬਿਨੇਟਰੀਅਲ ਸਮੱਸਿਆਵਾਂ ਦੇ ਵਿਚਕਾਰ ਸਮਾਧਾਨ" ਨਾਲ ਅੱਗੇ ਵਧਾਇਆ, ਜਿਸ ਵਿੱਚ ਉਸਨੇ ਦਿਖਾਇਆ ਕਿ 21 ਵੱਖੋ-ਵੱਖਰੀਆਂ ਕੰਬਿਨੇਟਰੀਅਲ ਅਤੇ ਗ੍ਰਾਫ ਸਿਧਾਂਤਕ ਸਮੱਸਿਆਵਾਂ, ਹਰੇਕ ਆਪਣੀ ਕੰਪਿਊਟੇਸ਼ਨਲ ਗੁੰਝਲਤਾ ਲਈ ਮਸ਼ਹੂਰ ਹਨ, ਐਨਪੀ-ਮੁਕੰਮਲ ਹਨ।
1972 ਵਿੱਚ ਰਿਚਰਡ ਕਾਰਪ ਦੁਆਰਾ ਲਿਖਿਆ ਗਿਆ ਪੇਪਰ ਕੀ ਹੈ ਜਿਸ ਨੇ ਇੰਟ੍ਰੈਕਟਬਿਲਿਟੀ ਅਤੇ ਐੱਨਪੀ-ਮੁਕੰਮਲ ਸਮੱਸਿਆਵਾਂ ਦੇ ਵਿਚਕਾਰ ਸਮਝ ਦੇ ਇੱਕ ਨਵੇਂ ਯੁੱਗ ਦੀ ਸ਼ੁਰੂਆਤ ਕੀਤੀ?