This isn't correct. What you may be remembering is that some (not all) NP comple... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

kalkin on Feb 25, 2024 | parent | context | favorite | on: Hallucination is inevitable: An innate limitation ...

This isn't correct. What you may be remembering is that some (not all) NP complete problems have limits on how accurately they can be approximated (unless P = NP). But approximation algorithms for NP complete problems form a whole subfield of CS.

moyix on Feb 25, 2024 [–]

The theorem that proves this is the PCP Theorem, in case anyone wants to read more about it: https://en.wikipedia.org/wiki/PCP_theorem#PCP_and_hardness_o...

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact