Rendered at 19:19:44 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
emil-lp 6 hours ago [-]
For those not familiar:
K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question.
The chromatic number of a graph is the lowest k for which it has a k-coloring.
Clearly, if you have an algorithm for one, you have an algorithm for the other.
The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number.
Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3.
There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).
2 hours ago [-]
aleph_minus_one 3 hours ago [-]
> Forests, trees, and bipartite graphs are 2-colorable.
More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition).
Since forests are bipartite, and trees are forests, the other two statements follow.
emil-lp 2 hours ago [-]
Precisely! The reason I mentioned trees and forests are because they are probably more familiar.
The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs: bipartite, or 2-partite are the graphs that can be partitioned into 2 (color)classes such that no edge is internally in a class.
More generally, the k-colorable graphs are exactly the k-partite graphs.
aleph_minus_one 1 hours ago [-]
> The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs
Be a little bit careful here: another common textbook definitions of bipartite graphs are:
- a graph is bipartite iff it has no odd circle.
- (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric.
I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that
graphs are conceptually very "similar" (k-colorable with different values for k).
But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable.
Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.
black_knight 6 hours ago [-]
At the end of brev paper there is a section on the LLM usage.
Now, this paper will undergo peer review. And thus, when published, we will trust the result as well as any other published result in mathematics. However, while humans are not infallible, LLMs have a tendency to spit out confident stuff which looks correct. Thus I worry when it is used this way to produce proofs. Peer review is not perfect, and may not be tuned to catch LLM’s style of errors.
There is a solution to this, which is to formalise the result and get it machine verified. And with LLMs, I daresay this is going to be best practice moving forward.
appplication 6 hours ago [-]
> Peer review is not perfect, and may not be tuned to catch LLM’s style of errors
This summarizes I think a lot of the challenges with validating LLM output. We hear “humans make mistakes too”, but I would agree with you that our human detection of human-made mistakes and LLM-made mistakes is unlikely to have the same coverage.
airstrike 4 hours ago [-]
The real problem is that human mistakes generally occur more frequently given the difficulty of the task, whereas LLM mistakes are somewhat random, like the carwash problem, because LLMs cannot truly reason.
I'd rather have a human on my team for whom I can reasonably surmise what tasks they're good at than have a robot who randomly gets shit wrong.
gus_massa 5 minutes ago [-]
> whereas LLM mistakes are somewhat random, like the carwash problem
At least in math problems, AI mistakes generally occur more frequently given the difficulty of the task.
The carwash problem is very undespecified. The question should be something like "I am American. I live in a single family home in a suburb. Each member of my family has their own car. All the cars are parked during the night at home. My boss don't authorize me to go during working hour outside the office. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?"
Disclaimer: I am Argentinean. I live in an old apartment building without a parking lot. I don't have a car, but if I had one I'd probably move to a building with parking inside or nearby. The closest professional car washing facility is like 1000 meters away, but the closest parking lot is like 50 meters away and they guys would wash the car for a few bucks. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?
yndoendo 3 hours ago [-]
I worded a questions similar to this with a person in the finance industry. He was very receptive of AI since it is one of the easiest ways to grow stock portfolio.
Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI?
drivebyhooting 4 hours ago [-]
Not much faster.
Any k-coloring algorithm of complexity F(n) can be used to create a chromatic number algorithm of complexity lg(N)F(N) simply by bisecting on N.
K-Coloring is the property that a graph can be colored with k colors such that no two neighboring nodes get the same color. The K-Coloring problem is a decision problem, ie a yes/no question.
The chromatic number of a graph is the lowest k for which it has a k-coloring.
Clearly, if you have an algorithm for one, you have an algorithm for the other.
The question was: is it faster to compute k-coloring than to compute its lowest (actual) k, ie its chromatic number.
Forests, trees, and bipartite graphs are 2-colorable. Planar graphs are 4-colorable. It is NP-complete to check if the chromatic number of a planar graph is 3.
There's a very interesting open problem, Hadwiger's conjecture that essentially says that the chromatic number is the clique (minor) number (whatever that means).
More precise: a graph is bipartite if and only if it is 2-colorable (this can actually be used as a definition).
Since forests are bipartite, and trees are forests, the other two statements follow.
The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs: bipartite, or 2-partite are the graphs that can be partitioned into 2 (color)classes such that no edge is internally in a class.
More generally, the k-colorable graphs are exactly the k-partite graphs.
Be a little bit careful here: another common textbook definitions of bipartite graphs are:
- a graph is bipartite iff it has no odd circle.
- (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric.
I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that
1-colorable, 2-colorable, 3-colorable, 4-colorable, ...
graphs are conceptually very "similar" (k-colorable with different values for k).
But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable.
Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.
Now, this paper will undergo peer review. And thus, when published, we will trust the result as well as any other published result in mathematics. However, while humans are not infallible, LLMs have a tendency to spit out confident stuff which looks correct. Thus I worry when it is used this way to produce proofs. Peer review is not perfect, and may not be tuned to catch LLM’s style of errors.
There is a solution to this, which is to formalise the result and get it machine verified. And with LLMs, I daresay this is going to be best practice moving forward.
This summarizes I think a lot of the challenges with validating LLM output. We hear “humans make mistakes too”, but I would agree with you that our human detection of human-made mistakes and LLM-made mistakes is unlikely to have the same coverage.
I'd rather have a human on my team for whom I can reasonably surmise what tasks they're good at than have a robot who randomly gets shit wrong.
At least in math problems, AI mistakes generally occur more frequently given the difficulty of the task.
The carwash problem is very undespecified. The question should be something like "I am American. I live in a single family home in a suburb. Each member of my family has their own car. All the cars are parked during the night at home. My boss don't authorize me to go during working hour outside the office. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?"
Disclaimer: I am Argentinean. I live in an old apartment building without a parking lot. I don't have a car, but if I had one I'd probably move to a building with parking inside or nearby. The closest professional car washing facility is like 1000 meters away, but the closest parking lot is like 50 meters away and they guys would wash the car for a few bucks. I want to wash my car. The car wash is 50 meters away. Should I walk or drive?
Say you have two assistant employees. One that reads the reports and one that uses AI to summarize the content. You are sitting in a high value meeting. You only can have one assistant with you in the meeting. Which one would you pick, the persons that read the reports or the person who only used AI?