Program Synthesis is ${\Sigma }_3^0$-Complete

Jinwoo Kim

This paper considers program synthesis in the context of computational hardness, asking the question: How hard is it to determine whether a given synthesis problem has a solution o…