Are Schur number compute NP hard

Stream: maths

[Alfredo Moreira-Rosa]

Following this video from Numberphile :
https://www.youtube.com/watch?v=57V8Ud7PL8k

I asked myself if we know if generating schur numbers is a NP hard proglem ? or there hope to find a better way than brute forcing compute them ?

[metakuntyyy]

Technically, you can always find a proof without brute forcing it. I also don't understand how you can reduce a solution of the computation of Schur numbers to other NP-complete problems. If you had an efficient algorithm that computes Schur numbers, would you be able to efficiently decide whether an arbitrary graph is 3-colorable?

[Alfredo Moreira-Rosa]

Good point. It's what triggered my question. Is it possible to reduce it to the 3-coloring problem ? I have not enough knowledge in this field to have an insight.

[metakuntyyy]

I think realistically the best we can hope are asymptotics and bounds. The Schur number of 6 seems to be out of reach.