On polynomial-time relation reducibility

DOI10.1215/00294527-3867118zbMath1425.03015OpenAlexW2186033963MaRDI QIDQ2364655

Su Gao, Caleb Ziegler

Publication date: 21 July 2017

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/91b4f8d5270b0ec608fef3bb09277c87650694e8

zbMATH Keywords

equivalence problempolynomial-time reducibilitykernel reducibilityrelation reducibilitystrong equivalence reducibility

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Primitive recursive equivalence relations and their primitive recursive complexity

This page was built for publication: On polynomial-time relation reducibility