Ask HN: What about the P=HP problem?

1 pointstoombowoombo1y ago3 comments

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?

Imagine this:

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).

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?

How would this approach change our current methods for verifying the accuracy of generated content in journalism, academia, and law?

What are the potential limitations or challenges in framing P = NP this way? What better models do you have?

3 comments

moritzwarhier1y ago

> 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?

What is the relation of this question to the actual definition of the P-NP-problem?

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.

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.

PaulHoule1y ago

“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”)

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.

al2o3cr1y ago

    Can every text generated quickly by an algorithm be quickly verified for truthfulness by a human or automated system?

The algorithm prints out "all the nontrivial zeros of the Riemann zeta function have a real part of 1/2". Good luck.

j / k navigate · click thread line to collapse