I've been thinking about a practical take on the P = NP problem. Traditionally, it's about whether problems that can be quickly verified by a computer can also be quickly solved by one. But what if we framed it in terms of human verification?<p>Imagine this:<p>P: Problems that can be quickly solved by algorithms on modern hardware.
HP: Problems where solutions can be quickly verified for truth by humans (or algorithms).<p>The real-life P = NP question: Can every text generated quickly by an algorithm (news summary, scientific claim, legal doc) be quickly verified for truthfulness by a human or automated system?<p>How would this approach change our current methods for verifying the accuracy of generated content in journalism, academia, and law?<p>What are the potential limitations or challenges in framing P = NP this way? What better models do you have?
> The real-life P = NP question: Can every text generated quickly by an algorithm (news summary, scientific claim, legal doc) be quickly verified for truthfulness by a human or automated system?<p>What is the relation of this question to the <i>actual definition</i> of the P-NP-problem?<p>Even adding the term "real-world", it seems to me like there is no connection at all, not even in a very broad, hand-wavy way.<p>As an steelman version of your problem, you could maybe relate it to the halting problem, but it's still way to far-fetched to make sense to me.
“Truth” is the most problematic concept in philosophy, it is so problematic that talk of “The Truth” is a warning that somebody is trying to pull the wool over your eyes. (See “Truther”)<p>I’d argue that many statements can only be truth tested with reference to a library or the ability to take measurements or do experiments. Many statements, such as “did I eat a 23 cm long carrot for lunch today?” are impossible to check because I ate the evidence.
<p><pre><code> Can every text generated quickly by an algorithm be quickly verified for truthfulness by a human or automated system?
</code></pre>
The algorithm prints out "all the nontrivial zeros of the Riemann zeta function have a real part of 1/2". Good luck.