pcstl

Fair, thank you.

I think you misunderstood, I believe they were requesting a layperson-friendly explanation of the conjecture and not a statement of it.

Sorry, you're correct. I meant "polynomial" rather than linear.

NP = nondeterministically polynomial. i.e. if you could evaluate all choices in parallel (or just "know" the right choice), then you'd get a polynomial runtime. That's what I was trying to informally hint at, but I ended up using the wrong term. I'll edit my original post.

That's equivalent to your description - the "hint" is knowing which of the options to choose.

The reason why superlinearity comes into play is that if you had a linearly growing amount of solutions to test then you'd just have a sum of polynomials, which is itself polynomial.

The exponential time hypothesis is essentially that NP-complete problems' best solutions are all exponential.

NP-complete problems are essentially those where you need to make some kind of choice over a superlinearly-growing set of options where each option can be solved in polynomial time. Like, for example, finding a route between cities on a map under a certain total distance. You might need to go over all choices of routes.

The ETH essentially assumes that the best solution (in terms of complexity, i.e. how it grows) you can get for these kinds of problems is exponential. OpenAI just proved that this is false, you can have solutions that are below exponential complexity (but still above polynomial - if anyone finds a polynomial solution then we'd have proven that P=NP)

*Can be solved

This proves that EXP != NP

This proves that EXP != NP, which was a stronger claim than P != NP.

In a way it shows that NP is perhaps less distant from P than imagined. Whether it can be _reduced_ to P in some gigabrain way, or whether that can be shown to be impossible remains to be seen.

It is definitely progress towards an answer to P ?= NP.

Since Graham's number is computable, it's an expected result even. The Busy Beaver sequence grows faster than any computable sequence.

Pretty much everyone who writes for a living and isn't doing "literature".

I.e. lawyers, accountants, clerks generally

There's a lot of weird, seemingly LLM-generated comments hyping the project here.

I think HN should start thinking seriously about more effective strategies to combat LLM-assisted astroturfing, if they aren't already.

None of this speaks about the quality of the project itself, but the fact that someone seems to be trying to manipulate me into caring about it makes me less inclined toward wanting to see anything relating to it.

Free.

Yes, it is. If you convince a model it is inside a sandbox it is much more likely to comply with requests that would normally be against its guardrails.

>assuming their difficulty is in the same ballpark

It is not. Many mathematicians have said that they don't expect to see solutions to the other 5 problems in their lifetimes.

Of course, AI might advance fast enough that the "in their lifetimes" part ends up wrong, but there is a considerable gap to the other problems. We have barely any idea of how to even get started on most of them.

Indeed.

Regression to the mean is pretty nasty. Stumbling into success can make you a car dealership owner or something like that, but being consistently successful in business requires just about as much skill as being consistently successful in, say, chess.

I find it difficult to imagine an intelligent person who finds it hard to get what they want. The trope of the oblivious genius who is incredibly competent in a single field of inquiry but completely unable to handle day-to-day life is more a creation of media than how reality works.