Hot answers tagged

4 votes

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

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 ...

Only top scored, non community-wiki answers of a minimum length are eligible