Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T22:48:32.352Z Has data issue: false hasContentIssue false

COMPLEXITY OF EQUIVALENCE RELATIONS AND PREORDERS FROM COMPUTABILITY THEORY

Published online by Cambridge University Press:  18 August 2014

EGOR IANOVSKI
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF OXFORD WOLFSON BUILDING, PARKS ROAD OXFORD OX1 3QD, UK.Email: egor.ianovski@cs.ox.ac.uk
RUSSELL MILLER
Affiliation:
DEPARTMENT OF MATHEMATICS, QUEENS COLLEGE 65-30 KISSENA BLVD., FLUSHING NY 11367 USA; & PH.D. PROGRAMS IN MATHEMATICS & COMPUTER SCIENCE CUNY GRADUATE CENTER, 365 FIFTH AVENUE, NEW YORK, NY 10016, USAE-mail: Russell.Miller@qc.cuny.edu
KENG MENG NG
Affiliation:
DIVISION OF MATHEMATICAL SCIENCES SCHOOL OF PHYSICAL & MATHEMATICAL SCIENCES NANYANG TECHNOLOGICAL UNIVERSITY 21 NANYANG LINK, SINGAPOREE-mail: kmng@ntu.edu.sg
ANDRÉ NIES
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE, UNIVERSITY OF AUCKLAND PRIVATE BAG 92019, AUCKLAND, NEW ZEALANDE-mail: andre@cs.auckland.ac.nz
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by

R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].

Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a ${\rm{\Pi }}_1^0$-complete equivalence relation, but no ${\rm{\Pi }}_k^0$-complete for k ≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$-complete. This includes polynomial time m-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2014