p!=np Because... we're anthropocentric!

[towforce]

So the main reason for believing that p!=np is anthropocentric: If p=np is true, a clever race like us would have solved it.

If I were trying to solve p=np, I would do so as follows:

1. Any random list of numbers is going to contain usable patterns (this is obvious and would be easy to prove)

2. It's possible to find these patterns in polynomial time (this is more challenging)

Those two steps would not constitute a whole proof, but they would be a good step. Given that all p=np combinatorial tasks are reducible to SAT (boolean satisfiability) the completion of the proof would be demonstrating that a usable pattern for the solution could be generated in polynomial time from a CNF model.

On Topic: this goes to the solvability of chess, or at least the ability to find deep (complex) patterns which make playing the game well quick and easy.

[towforce]

2. It's possible to find these patterns in polynomial time (this is more challenging)

Some ideas for this off the top of my head:

* Fast Fourier Transform / Fast Multipole Methods

* Spline interpolation

* Least squares polynomial regression (if resolving a CNF for example, no need for the numbers to be accurate - they only have to differentiate between zero and one). There are other ways to do polynomial approximations which would probably be better suited here

[chrisw]

If I were trying to solve p=np, I would do so as follows:

1. Any random list of numbers is going to contain usable patterns (this is obvious and would be easy to prove)
........

On Topic: this goes to the solvability of chess, or at least the ability to find deep (complex) patterns which make playing the game well quick and easy.

Utterly ridiculous. Of course in any random list of numbers there will be random patterns (whether "useable" or not is another matter). The problem isn't finding random patterns in lists THAT HAVE ALREADY BEEN GENERATED, it's in finding the next number that would follow in an as yet to be generated random sequence.

Here's a random sequence from a massive random number generator. As you can see it contains a pattern of consecutive zeros:

01110101010101101010100000000000000000000000101101101010101010

Tell us the NEXT number in the sequence.

Which makes your claim to get your one trick pony topic back into talkchess on the grounds of on-topic quite spurious.

[towforce]

Utterly ridiculous. Of course in any random list of numbers there will be random patterns (whether "useable" or not is another matter). The problem isn't finding random patterns in lists THAT HAVE ALREADY BEEN GENERATED, it's in finding the next number that would follow in an as yet to be generated random sequence.

Here's a random sequence from a massive random number generator. As you can see it contains a pattern of consecutive zeros:

01110101010101101010100000000000000000000000101101101010101010

Tell us the NEXT number in the sequence.

Which makes your claim to get your one trick pony topic back into talkchess on the grounds of on-topic quite spurious.

Many years ago, I did write a webpage using JavaScript to play the game of matching pennies. It found the previous best matching string of same/change to the current one. There were other algorithms that played the game better.

Predicting the next token in a sequence is more related to LLMs than to resolving P=NP. For an LLM the computational process of generating a good response is fundamentally an exercise in stochastic modelling - using probability to navigate a massive geometric space of meaning.

Regarding SAT (Boolean Satisfiability) as the best example of a P=NP problem, there are many good algorithms for solving it, but at this time none of them work well for all CNF models. Solving SAT would not be a game of predicting the next token (or binary bit in this case) in a sequence. There are many ways to solve it, but the way I discussed in the OP was to find a pattern from the CNF model that would generate the sequence.

[towforce]

Utterly ridiculous. Of course in any random list of numbers there will be random patterns (whether "useable" or not is another matter). The problem isn't finding random patterns in lists THAT HAVE ALREADY BEEN GENERATED, it's in finding the next number that would follow in an as yet to be generated random sequence.

Here's a random sequence from a massive random number generator. As you can see it contains a pattern of consecutive zeros:

01110101010101101010100000000000000000000000101101101010101010

Tell us the NEXT number in the sequence.

Which makes your claim to get your one trick pony topic back into talkchess on the grounds of on-topic quite spurious.

Many years ago, I did write a webpage using JavaScript to play the game of matching pennies. It found the previous best matching string of same/change to the current one.

Just for fun, using this algorithm predicts the next number to be 1:

* the last 10 digits of the sequence is 1010101010

* there is a matching sequence in items 4-13 of the sequence

* item 14 of the sequence is 1

* if you take the last 11 digits of the sequence, there is not match for that in the string

[towforce]

Btw, the best algorithm I have seen for playing matching pennies (or, to put it another way, to guess the next binary digit in a list, per Chris's post above) is universal conditional consistency - link. A web page based on this algorithm handily beats all other algorithms for playing this game.

The natural question is, could this be used to predict tokens in a language model? You'd have to overcome the following challenges:

1. Express all knowledge as lists of binary decisions
2. Each query would have to be run against the entire database of training data

So the answer for now is "no".

[towforce]

It's easy to think that an algorithm to generate a list of truly random binary digits could well need as many parts as the length of the list itself - but maybe not: the digits don't need high accuracy - just enough to differentiate 1 from 0 - so approximation methods may be usable

In SAT (boolean satisfiability) the CNF likely contains more information about the relationships between the digits than is first apparent: the performance of SAT solvers jumped by an order of magnitude in 1996 when the CDCL algorithm was introduced.

Schaefer's dichotomy theorem (link) implies that if p=np that SAT can be solved in polynomial time (and vice versa). Maybe SAT can be improved by (1) using approximation methods that are accurate enough to give the actual answer (2) maybe there are better ways than CDCL to extract the relationships between the clauses than CDCL: we know that conditional probability works well (it enables the navigation in a large geometric space of meaning in an LLM), or maybe the key is a better method than CDCL of generating a large number of constraints from the CNF model before starting to look for solutions.

I understand that people here are most interested in what has been proven to work - but this goes to the fundamental question of what would work to solve games like chess, or even the Ruliad.