Hacker News

points by mlinsey 3 days ago | 0 comments

I understand that the Exponential Time Hypothesis being false doesn't necessarily mean P=NP, but for people who are a lot more knowledgeable about complexity theory, does this update your priors significantly in the direction of P=NP?

[–] jltsiren 3 days ago

It's been a long time since I seriously thought about complexity theory, but I'd say no. For similar reasons to why complexity class E is not closed under polynomial-time reductions.

The most important component in the time bound is of the form 2^{n / polylog(n)}, which is subexponential. But if you have reduction from another problem that increases instance size quadratically, the algorithm for the other problem is no longer subexponential. Which means we are still essentially in the same neighborhood as before.

It's a huge result if true, and probably the first major AI result that affects the papers I read. But since the boundary in the hypothesis was kind of arbitrary, breaching it should not significantly change our intuition on complexity classes.

[–] hakuseki 3 days ago

I think the bigger issue (for someone hoping for P=NP) is that there's a huge gap between "polynomial" and "exponential." Even if it were the case that all NP problem classes had subexponential decision algorithms, that would not get us close to P=NP.

[–] cwillu 3 days ago

How much effort has been expended on optimizing those reductions though? I have a harder time believing that one can hang one's belief in P!=NP on that particular hook.

[–] rao-v 3 days ago

There are so many just barely sub-exponential function shapes between 2^(n / sqrt ln n) {this result} and 2^(log n) {polynomial time}!

[–] jltsiren 3 days ago

The challenge is the initial reduction from an arbitrary problem in NP to the problem you want to prove NP-complete.

In the usual approach, you assume a nondeterministic Turing machine (or equivalent) that solves the problem and a time bound (which can be an arbitrarily large polynomial). You then create a boolean expression that can be satisfied if and only if the Turing machine accepts the original problem instance. Unfortunately all constructions so far have included the time bound as a factor of the size of the expression.

[–] ComplexSystems 3 days ago

I think that it'd be funny if the polynomial time SAT solver was just "send your SAT instance to Astra and have it try to solve it for a few hours."

[–] GuB-42 3 days ago

I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.

Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.

[–] ViscountPenguin 3 days ago

Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?

[–] anon291 3 days ago

For the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).

A single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.

Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.

[–] geraneum 3 days ago

The context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.

[–] GuB-42 2 days ago

It depends on what you say is O(1). A theoretical Turing machine has an infinite tape that can be accessed in O(1), but in real life, it would require a machine of an infinite size.

Same idea for that transformer, it needs an infinite context, and it is an infinitely big machine, but with that level of abstraction, it processes a token in O(1).

In practice, there is no such thing as O(1) on arbitrarily sized data, there is no such thing as infinity either, it is just an abstraction.

[–] geraneum 2 days ago

> Same idea for that transformer

It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.

In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.

Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?

[–] vidarh 3 days ago

The context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.

So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).

[–] geraneum 2 days ago

Any basic lookup table is turing complete if you bolt an external infinite tape and read/write head onto it. But then that’s moving the goal post since the context wouldn’t be the “limitless tape” and it’s not a transformer “in the normal way” because turing completeness would be coming from external io and not from auto regressive self attention. Different topic.

[–] vidarh 2 days ago

The point is that the discussion is essentially entirely meaningless, as it's pretty much hard to implement any simple construct that can make deterministic decisions based on a data stream and wrap it in a loop without ending up with a UTM.

The consequence of that is that the original question GuB-42 raised is pretty pointless too. An "inert" transformer effectively has limitations, but as typically used it trivially becomes Turing complete, and so the class of problems it can solve is the exact same class of problems almost any of our other computational devices can solve.

And if you want to point out that this externalises all of what actually matters if we are talking about e.g. intelligence, then yes, it does. But by extension you can trade complexity of the tape for complexity of the machine, and so you can internalise any part of the problem that can be solved with a finite section of tape as a single state transition (trivial proof: For a given machine M with finite state, you can make your machine N execute those steps as a single state transition by having N run M on a state transition.)

To extend that to where I assume they'd want to go in the first place: A transformer wrapped in a loop with access to "just" a "tape head" can "only" be limited from being theoretically able to get all the way to human level intelligence if human brains depend on computations that exceed the Turing computable. But that is no different from any other Turing complete device.

Of course that says nothing of whether it's a practical way of getting there.

[–] anon291 3 days ago

It's not contradictory at all. The dfa at each step of the turing machine model is also o(1).

[–] geraneum 3 days ago

Of course it is. You’re conflating a turing machine with a transformer. Transformers don’t have a local read/write head. The [self] attention is over the whole context, which makes each step O(N) at best (with caching) and O(N^2) w/o.

[–] anon291 2 days ago

of course it has a read write head. In fact it has N read / write heads equal to the size of the context since each latent state is updated with the results of the cross attention mechanism at each step.

Alternatively, you can view the '<unknown>' token that is dynamically driven to the embedding of the output token to be the write head. Either way, the simple truth is that you can train a transformer system (i.e., an iteratively applied transformer) to simulate an arbitrary turing machine.

[–] varjag 3 days ago

Imagine you're trying to prove that water is wet (P!=NP). You lack a formalism that could make sense at building a proof even though pretty much everyone agrees from empirical evidence that the water is indeed wet. A promising attempt at building one such formalism was just demonstrated by a model to be a dead end.

[–] jaaron 3 days ago

I like this, but the actual finding is a bit different. Trying to keep the water is wet makes this awkward, but I believe it's more like:

Everyone agrees that water is wet (P!=NP), but no one can prove it. In the meantime, a whole field of computer science was built on a stronger belief (ETH): that water, at its worst, soaks. Turns out, even at its worst, water only makes things damp. It's still wet. That said, this finding did produce a new measurement of wetness.

[–] pizzafeelsright 3 days ago

At certain temperatures water is indeed not wet.

[–] grumbelbart2 2 days ago

Some say water is never wet, it makes wet.

[–] zeroonetwothree 3 days ago

A nontrivial % believe P = NP with some reasonable probability. I wouldn’t say it’s all that settled unlike say RH

[–] kibwen 3 days ago

Anyone credible? A nontrivial number of people also believe that humans used to ride dinosaurs around like in the Flintstones.

[–] aleph_minus_one 3 days ago

> Anyone credible [who believes P=NP with some reasonable probability?

Do you accept

- Moshe Y. Vardi [1]

- Anil Nerode [2]

- Donald Knuth [3]

to be credible? Source for the statements that they consider P=NP to be possible: [4]

And you may include me in the list of credible P=NP believers because treat myself as a credible authority, i.e. when I ask myself whether something is right, I consider myself to be much more credible than some famous scientist. ;-)

(to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems. One should consider the evidence by oneself instead of believing in P!=NP because lots of computer scientists claim all the time that this is likely true, or consider P=NP now to be possible just because some famous computer scientists consider it to be possible)

---

[1] https://en.wikipedia.org/w/index.php?title=Moshe_Vardi&oldid...

[2] https://en.wikipedia.org/w/index.php?title=Anil_Nerode&oldid...

[3] https://en.wikipedia.org/w/index.php?title=Donald_Knuth&oldi...

[4] https://en.wikipedia.org/w/index.php?title=P_versus_NP_probl...

[–] jibalt 3 days ago

Note that, while Knuth believes that P = NP, he doesn't believe that it will have practical applications because the exponents and/or constants will be galactic.

> to be very clear: the previous paragraph is rather a clear statement against this kind of "hero worship" with respect to mathematical or scientific problems.

No, it's an irrational rejection of the notion of expertise. The experts are not "heroes", they are simply people who have done vastly more study than folks like you or me. e.g., if Magnus Carlsen looks at a complex chess position and says that white is winning, I will trust his judgment far more than my own.

[–] lioeters 3 days ago

> The main argument in favor of P ≠ NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. — Moshe Y. Vardi

That sounds particularly relevant in how AI-assisted/driven mathematical research is changing the game, where previous assumptions based on human experience/effort are being overturned unexpectedly.

[–] eluru 3 days ago

stack overflow worthy levels of ego

[–] carefree-bob 3 days ago

I'm beginning to wonder whether P!=NP is undecidable.

[–] teiferer 2 days ago

That statement is nonsensical for the usual formal notion of "undecidable" which is about infinite sets of inputs that a machine is asked to classify as "yes" or "no" instances, also called a decision problem.

P-vs-NP is no such decision problem. It has a single instance, we just don't know its validity.

[–] IAmBroom 2 days ago

It was not a formal statement.

[–] vbezhenar 3 days ago

Water is not wet. Human lacks water sensor. All the sensors we have a temperature ones so we sense "wet" as a combination of temperature and visual information. Close your eyes, touch water of your skin temperature and you won't sense it. It's not wet.

[–] foo12bar 3 days ago

Stick your head in it and breathe. You'll know.

[–] pmontra 3 days ago

Sand too, even when dry. But OK, metaphors have limits.

[–] jibalt 3 days ago

Not only is that statement not true, as noted by others, it's also not at all relevant to what you're responding to.

[–] foo12bar 2 days ago

Oh, so if you stick your head in a liquid and breathe you wouldn't know?

[–] teiferer 2 days ago

Sticking your head into non-liquid substances can have the same outcome. It therefore is not a suitable method for detecting wetness.

[–] foo12bar 2 days ago

I'm not talking about outcome, but of sensing. I also never wrote it was a suitable method. When did that become a requirement?

I kist thought it was interesting that there are receptors that can detect wetness, just not on the skin. It was a joke pointing that out.

Fuck.

[–] stavros 3 days ago

By that definition, a vacuum is wet.

[–] foo12bar 2 days ago

Trying to beathing in a vacuum would not feel the same as breathing in a liquid.

[–] stavros 2 days ago

What would feel different?

[–] foo12bar 2 days ago

Im a vacuum you would not be choking.

[–] aleph_minus_one 3 days ago

There exist lots of non-wetting liquids in which humans cannot breathe.

[–] foo12bar 2 days ago

Your lungs have sensors that can detect being coated by a liquid which invokes coughing. In that sense, you can detect wetness.

[–] teiferer 2 days ago

They detect being coated, no matter liquid or not. (Source: Parents who smoke. And don't tell me the crap they are inhaling is a liquid.)

[–] foo12bar 2 days ago

Secondhand smoke does not feel the same as drowning.

[–] pizzafeelsright 3 days ago

Fog, clouds, steam, ice.

[–] manquer 3 days ago

Not the best analogy; water is famously not wet; it makes a surface wet is the common consensus ; wetness is being a property of a surface

[–] tavavex 3 days ago

No, it is famously a pointless internet debate with no settled answer. There is no scientific definition of what can or can't be wet, saying that wetness only applies to surfaces is just an opinion. It's an entirely linguistic question, and most people would say water is wet. If you want more than descriptivism, the common definition is something like 'containing or being covered with liquid', and I think most people would agree that a mass of water contains water.

[–] jibalt 3 days ago

No. Scott Aaronson said that it changed it from 3% to 5% for him, which is a lot more generous than I would be (but he knows far more about the subject than I do).

[–] randallsquared 3 days ago

So, what I heard was "No, and here is a good reason it should be 'yes, some'."

[–] jibalt 3 days ago

The question was

> does this update your priors significantly in the direction of P=NP?

My answer is no ... and Aaronson's answer would also be no ... clearly he doesn't view a change from 3% to 5% to be significant ... his response downplayed the significance of !ETH in re NP?=P. So apparently you downvoted me for simply stating my own opinion while you completely misunderstood what it was an opinion of.

[–] baobabKoodaa 3 days ago

A change from 3% to 5% is significant. It's almost doubling the probability.

[–] maybeOneDay 2 days ago

Buying two lottery tickets doubles your probability of winning. Does it significantly move your priors?

[–] baobabKoodaa 2 days ago

Yes, it doubles the probability that I win the lotto. Yes, doubling a probability is significant. I'm not sure you're using the term "prior" correctly here, though.

[–] maybeOneDay 1 day ago

The "prior" is "am I going to win the lottery". It's borderline facetious to argue that buying two tickets significantly affects your probability.

[–] zarzavat 3 days ago

It might make the third option, that P vs NP cannot be proven true or false, somewhat less likely.

[–] teiferer 2 days ago

Could you elaborate?

[–] CaptainNegative 3 days ago

I think it would have to if you're honest with yourself. Any proof of a novel implication of P=NP, such as !ETH, should increase your belief in the two sets' equality. Just as any novel implication of P≠NP should adjust your belief the other way.

My thesis was around showing implications of few different hardness conjectures. So grounded was ETH that I introduced it in a side note as Conjecture 0 after Conjectures 1 and 2. I don't think it's easy to express how substantial of a Bayesian update this is all around.

[–] novaRom 3 days ago

For me, this result is significant. It basically adds much more hope P is equal NP (that majority seems being against). I believe one day AI will explain a major flaw in modern mathematics, so a kind of correction in axioms will be suggested to prove Rieman's hypothesis (or a completely new apparatus)

[–] rcpt 3 days ago

I don't know if that's a "flaw". It's what Godel Incompleteness guarantees.

Would be funny if the most famous problem turns out be an example though

[–] skew-aberration 3 days ago

That's not that how that works btw. The incompleteness is a property of the algorithm which does the proofs, not the theorems. If a theorem is true it has a proof and a program which proves it (printf("the proof verbatim")). But no computer program can successfully prove all theorems. The space of potential proofs is too big to search systematically, but you can still get lucky.

[–] noslenwerdna 3 days ago

That is also not how it works. The theorem says that there exist some true statements for which there is no proof. This is assuming the axioms are consistent.

[–] skew-aberration 3 days ago

I think you're right, I'm conflating two separate things.

EDIT: I am wrong (it's been a while) but there is nuance.

I said any computer program fails to prove some true statements. In fact, some 'true' statements cannot be proven by any program, as others have said.

But for those statements G, you can prove 'G is true if our system is consistent', just not 'G is true'.

So when we say G is 'true', we are really just asserting the consistency axiom that our computer program is denied.

[–] rcpt 3 days ago

Godel says that there are statements that are true but have no proof within that system. It's not about algorithms.

I'm saying it'd be funny if Riemann were true but not proveable.

Though I guess it's actually funnier. If Riemann were false then there would be a counterexample, so it's clearly within existing axioms.

So if one can prove that Riemann isn't proveable in our current axioms then it has to be true.

[–] plagiarist 3 days ago

Can something be both true and unprovable without being a self-referential Godel sentence? I assume most statements that aren't self-referential are independent, like the continuum hypothesis with ZFC.

[–] skew-aberration 3 days ago

Godel sentences are only true if you assume consistency. And once you add that axiom, the computer can prove them too.

G is independent of your original system T (cannot be proven true or false).

If you create T+ with added consistency axiom, then G is true and provable.

But G is never true and unprovable in the same system.

It's a lot like is/ought or theology.

[–] _dain_ 3 days ago

Why do you "hope" P=NP? It would be a catastrophe

[–] jibalt 3 days ago

Either P=NP or not. Hoping one way or the other changes nothing. Nor does it change how efficient computing is, nor does it have any effect on cryptography. Discovering a vastly more efficient means of factoring primes--perhaps via quantum computing--would do that. But just learning that P=NP does nothing to further such a discovery. Almost certainly, if P=NP, the exponents and/or constants in a polynomial factoring algorithm would be galactic. (FWIW, Knuth believes that P=NP and that it has no practical consequences.)

[–] coliveira 3 days ago

Why? Nature doesn't care if people are making financial transactions based on flawed cryptography.

[–] 80fj0348i 3 days ago

Have you been in nature? It's cold and full of bugs and disease.

[–] rcpt 3 days ago

Not really. P=NP but the degree of the polynomial is Grahams number doesn't let people into your bank account

[–] andriy_koval 3 days ago

it could make lots of compute way more efficient, not sure why it is catastrophe..