10 citations · 68 across the 40 of their papers we have counts for
5 papers · 1 filter
Ramsey-type graph coloring and diagonal non-computability
Ludovic Patey
A function is diagonally non-computable (d.n.c.) if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomnes…
Degrees bounding principles and universal instances in reverse mathematics
Ludovic Patey
A Turing degree d bounds a principle P of reverse mathematics if every computable instance of P has a d-computable solution. P admits a universal instance if there exists a computa…
Diagonally non-computable functions and fireworks
Laurent Bienvenu, Ludovic Patey
A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be neg…
On the logical strengths of partial solutions to mathematical problems
Laurent Bienvenu, Ludovic Patey, Paul Shafer
We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to…
The complexity of satisfaction problems in reverse mathematics
Ludovic Patey
Satisfiability problems play a central role in computer science and engineering as a general framework for studying the complexity of various problems. Schaefer proved in 1978 that…