4
votes
Accepted
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
This class was defined in Papadimitriou's original 1994 paper, that also introduced the class PPAD, and it is known as PPADS. There is an oracle separation between the two classes. For a recent paper ...
- 13.8k
1
vote
Accepted
Short UNSAT Certificates for X3SAT
I can now prove my conjecture is false. The unsatisfiable 4 Pigeons in 3 Holes problem, when converted to linear, monotone X3SAT, does not have any completely blocked Conflict Clusters.
A conflict ...
- 519
Only top scored, non community-wiki answers of a minimum length are eligible