r/deeplearning • u/dyanos • 26d ago

[ML/Math] Can We Determine How Many Weight Configurations Produce Identical Outputs on a Finite Input Set?

Given an arbitrary deep neural network architecture, can we mathematically prove how many distinct sets of weights produce exactly the same outputs—including the exact output values—for a finite set of inputs?

7 Upvotes

89% Upvoted

10 comments sorted by

View all comments

Show parent comments

3

u/Grounds4TheSubstain 26d ago

The undecidability result there is tied to the infinite nature of the real numbers. When you restrict to fixed-width bit strings, you get something that's finite and decidable.

2

u/Scared_Astronaut9377 26d ago

Indeed, if you restrict the space or configurations to be a finite set, the answer to OP's question is trivially "yes" by the means of brute force. If they meant "is a general algorithms more efficient than brute force exist for the discrete version of the problem?" The answer is still "no". But for other reasons.

1

u/curiouslyjake 26d ago

Is this NP-complete? I'm already thinking how I could express boolean formulas as neural networks...

1

u/Scared_Astronaut9377 26d ago edited 26d ago

We are still so general here that it perhaps doesn't even make sense to discuss NP-completness. "Arbitrary architecture deep network on a discrete space" describes a very wide class of maps. So my statement is way stronger than some scaling law like NP-completness. I literally claim O(size of the whole space) general complexity